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
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!
