The Canadian Traveller Problem is a PSPACE-complete optimization problem where a traveller traverses an undirected weighted graph G from source s to target t where some edges \(E_*\) are blocked. At the beginning, the traveller does not know which edges are blocked. He discovers them when arriving at one of their endpoints. The objective is to minimize the distance traversed to reach t.
Westphal proved that no randomized strategy has a competitive ratio smaller than \(\left| E_* \right| +1\). We show, using linear algebra techniques, that this bound cannot be attained, especially on a specific class of graphs: apex trees. Indeed, no randomized strategy can be \(\left( \left| E_* \right| +1\right) \)-competitive, even on apex trees with only three simple \((s,t)\)-paths.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Springer Professional "Wirtschaft+Technik"
Online-Abonnement
Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:
Mit dem Technik-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 40.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:
Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:
Bar-Noy, A., Schieber, B.: The Canadian Traveller Problem. In: Proceedings of ACM/SIAM SODA, pp. 261–270 (1991)
2.
Bender, M., Westphal, S.: An optimal randomized online algorithm for the k-Canadian Traveller Problem on node-disjoint paths. J. Comb. Optim.
30(1), 87–96 (2015)
MathSciNetCrossRef
3.
Bergé, P., Hemery, J., Rimmel, A., Tomasik, J.: On the competitiveness of memoryless strategies for the k-Canadian Traveller Problem. Inform. Proces. Lett. (submitted)
4.
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York, USA (1998)
5.
Demaine, E.D., Huang, Y., Liao, C.-S., Sadakane, K.: Canadians should travel randomly. In: Proceedings of ICALP, pp. 380–391 (2014)
6.
Farkas, J.: Uber die Theorie der Einfachen Ungleichungen. J. fur die Reine und Angewandte Math.
124, 1–27 (1902)
7.
Matousek, J., Gärtner, B.: Understanding and Using Linear Programming. Springer, New York, USA (2006)
MATH
8.
Papadimitriou, C., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci.
84(1), 127–150 (1991)
MathSciNetCrossRef
9.
Westphal, S.: A note on the k-Canadian Traveller Problem. Inform. Proces. Lett.
106(3), 87–89 (2008)
MathSciNetCrossRef
Über dieses Kapitel
Titel
The Competitiveness of Randomized Strategies for Canadians via Systems of Linear Inequalities
Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.
Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis. Jetzt gratis downloaden!
