On the competitiveness of memoryless strategies for the \(k\)-Canadian traveller problem. (English) Zbl 1522.90149
Kim, Donghyun (ed.) et al., Combinatorial optimization and applications. 12th international conference, COCOA 2018, Atlanta, GA, USA, December 15–17, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11346, 566-576 (2018).
Summary: The \(k\)-Canadian Traveller Problem \((k\)-CTP), proven PSPACE-complete by Papadimitriou and Yannakakis, is a generalization of the Shortest Path Problem which admits blocked edges. Its objective is to determine the strategy that makes the traveller traverse graph \(G\) between two given nodes \(s\) and \(t\) with the minimal distance, knowing that at most \(k\) edges are blocked. The traveller discovers that an edge is blocked when arriving at one of its endpoints.
We study the competitiveness of randomized memoryless strategies to solve the \(k\)-CTP. Memoryless strategies are attractive in practice as a decision made by the strategy for a traveller in node \(v\) of \(G\) does not depend on his anterior moves. We establish that the competitive ratio of any randomized memoryless strategy cannot be better than \(2k + O(1) \). This means that randomized memoryless strategies are asymptotically as competitive as deterministic strategies which achieve a ratio \(2k+1\) at best.
For the entire collection see [Zbl 1407.68037].
We study the competitiveness of randomized memoryless strategies to solve the \(k\)-CTP. Memoryless strategies are attractive in practice as a decision made by the strategy for a traveller in node \(v\) of \(G\) does not depend on his anterior moves. We establish that the competitive ratio of any randomized memoryless strategy cannot be better than \(2k + O(1) \). This means that randomized memoryless strategies are asymptotically as competitive as deterministic strategies which achieve a ratio \(2k+1\) at best.
For the entire collection see [Zbl 1407.68037].
References:
| [1] | Albers, S., Online algorithms: a survey, Math. Program., 97, 3-26, 2003 · Zbl 1035.68136 · doi:10.1007/s10107-003-0436-0 |
| [2] | Bar-Noy, A., Schieber, B.: The Canadian traveller problem. In: Proceedings of ACM/SIAM SODA, pp. 261-270 (1991) · Zbl 0800.68642 |
| [3] | 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 · Zbl 1325.90094 · doi:10.1007/s10878-013-9634-8 |
| [4] | Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis, 1998, Cambridge: Cambridge University Press, Cambridge · Zbl 0931.68015 |
| [5] | Demaine, ED; Huang, Y.; Liao, C-S; Sadakane, K.; Esparza, J.; Fraigniaud, P.; Husfeldt, T.; Koutsoupias, E., Canadians should travel randomly, Automata, Languages, and Programming, 380-391, 2014, Heidelberg: Springer, Heidelberg · Zbl 1412.68298 · doi:10.1007/978-3-662-43948-7_32 |
| [6] | Papadimitriou, C.; Yannakakis, M., Shortest paths without a map, Theor. Comput. Sci., 84, 1, 127-150, 1991 · Zbl 0733.68065 · doi:10.1016/0304-3975(91)90263-2 |
| [7] | Westphal, S., A note on the k-Canadian traveller problem, Inform. Proces. Lett., 106, 3, 87-89, 2008 · Zbl 1186.68570 · doi:10.1016/j.ipl.2007.10.004 |
| [8] | Xu, Y.; Hu, M.; Su, B.; Zhu, B.; Zhu, Z., The Canadian traveller problem and its competitive analysis, J. Comb. Optim., 18, 2, 195-205, 2009 · Zbl 1173.90524 · doi:10.1007/s10878-008-9156-y |
| [9] | Yao, A.C.: Probabilistic computations: toward a unified measure of complexity. In: Proceedings of FOCS, pp. 222-227 (1977) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
