Multiple Canadians on the road: minimizing the distance competitive ratio

Pierre Bergé, Jean Desmarchelier, Wen Guo, Aurélie Lefebvre, Arpad Rimmel and Joanna Tomasik ()
Additional contact information
Pierre Bergé: Université Paris-Sud, Université Paris-Saclay
Jean Desmarchelier: Université Paris-Saclay
Wen Guo: Université Paris-Saclay
Aurélie Lefebvre: Université Paris-Saclay
Arpad Rimmel: Université Paris-Saclay
Joanna Tomasik: Université Paris-Saclay

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 7, 1086-1100

Abstract: Abstract The online k-Canadian Traveller Problem ( $$k$$ k -CTP), known to be PSPACE-complete, asks for the best strategy a traveller has to follow in order to traverse with minimum distance a graph from s to t where at most k edges are blocked. A blocked edge is revealed when the traveller visits one of its endpoints. It is proven that for any deterministic strategy, the competitive ratio is larger than $$2k+1$$ 2 k + 1 . Indeed, the distance traversed by the traveller is potentially greater than $$2k+1$$ 2 k + 1 times the optimal journey. For randomized strategies, this ratio becomes $$k+1$$ k + 1 . We complement the work of Zhang et al. on $$k$$ k -CTP with multiple travellers by evaluating the distance competitive ratio of deterministic and randomized strategies for complete and partial communication. We compare these ratios with two other communication levels: when travellers do not communicate at all and when they communicate only before beginning to move. Eventually, we provide a wide picture of the distance competitiveness reachable for the $$k$$ k -CTP in function of the number of travellers and communication levels.

Keywords: Canadian Traveller Problem; Communication; Competitive analysis (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00438-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:4:d:10.1007_s10878-019-00438-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00438-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().