Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Multiple Canadians on the road: minimizing the distance competitive ratio

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

The online k-Canadian Traveller Problem (\(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\). Indeed, the distance traversed by the traveller is potentially greater than \(2k+1\) times the optimal journey. For randomized strategies, this ratio becomes \(k+1\). We complement the work of Zhang et al. on \(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\)-CTP in function of the number of travellers and communication levels.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Bar-Noy A, Schieber B (1991) The Canadian Traveller Problem. In: Proceedings of ACM/SIAM SODA, pp 261–270

  • Bender M, Westphal S (2015) An optimal randomized online algorithm for the k-Canadian Traveller Problem on node-disjoint paths. J Comb Optim 30(1):87–96

    Article  MathSciNet  Google Scholar 

  • Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  • Demaine ED, Huang Y, Liao CS, Sadakane K(2014) Canadians should travel randomly. In: Proceedings of ICALP, pp 380–391

    Chapter  Google Scholar 

  • Papadimitriou C, Yannakakis M (1991) Shortest paths without a map. Theor Comput Sci 84(1):127–150

    Article  MathSciNet  Google Scholar 

  • Shiri D, Sibel Salman F (2017) On the online multi-agent O–D k-Canadian Traveler Problem. J Comb Optim 34(2):453–461

    Article  MathSciNet  Google Scholar 

  • Westphal S (2008) A note on the k-Canadian Traveller Problem. Inf Process Lett 106(3):87–89

    Article  MathSciNet  Google Scholar 

  • Zhang H, Xu Y, Qin L (2011) The k-Canadian Travelers Problem with communication. J Comb Opt 26:251–265

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LRI, Université Paris-Sud, Université Paris-Saclay, 91405, Orsay Cedex, France

    Pierre Bergé

  2. CentraleSupélec, Université Paris-Saclay, 91190, Gif-sur-Yvette, France

    Jean Desmarchelier, Wen Guo & Aurélie Lefebvre

  3. LRI, CentraleSupélec, Université Paris-Saclay, 91405, Orsay Cedex, France

    Arpad Rimmel & Joanna Tomasik

Authors
  1. Pierre Bergé
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean Desmarchelier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wen Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Aurélie Lefebvre
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Arpad Rimmel
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Joanna Tomasik
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joanna Tomasik.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bergé, P., Desmarchelier, J., Guo, W. et al. Multiple Canadians on the road: minimizing the distance competitive ratio. J Comb Optim 38, 1086–1100 (2019). https://doi.org/10.1007/s10878-019-00438-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-019-00438-6

Keywords

Search

Navigation