Canadian Traveller Problem with Predictions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Canadian Traveller Problem with Predictions

  • Conference paper
  • First Online:
Approximation and Online Algorithms (WAOA 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13538))

Included in the following conference series:

  • 485 Accesses

Abstract

In this work, we consider the k-Canadian Traveller Problem (k-CTP) under the learning-augmented framework proposed by Lykouris & Vassilvitskii [23]. k-CTP is a generalization of the shortest path problem, and involves a traveller who knows the entire graph in advance and wishes to find the shortest route from a source vertex s to a destination vertex t, but discovers online that some edges (up to k) are blocked once reaching them. A potentially imperfect predictor gives us the number and the locations of the blocked edges.

We present a deterministic and a randomized online algorithm for the learning-augmented k-CTP that achieve a tradeoff between consistency (quality of the solution when the prediction is correct) and robustness (quality of the solution when there are errors in the prediction). Moreover, we prove a matching lower bound for the deterministic case establishing that the tradeoff between consistency and robustness is optimal, and show a lower bound for the randomized algorithm. Finally, we prove several deterministic and randomized lower bounds on the competitive ratio of k-CTP depending on the prediction error, and complement them, in most cases, with matching upper bounds.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    As mentioned in earlier, while a \((2k+1)\)-competitive (matching the lower bound) deterministic algorithm is known for general graph, a \((k+1)\)-competitive randomized algorithm (matching the lower bound) is only known for path-disjoint graphs.

  2. 2.

    If the graph contains less than k disjoint paths, then choose the maximum number of paths \(l < k\) and run RandBacktrack with parameter \(l-1\). The analysis remains the same.

References

  1. Antoniadis, A., Coester, C., Eliás, M., Polak, A., Simon, B.: Online metric algorithms with untrusted predictions. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13–18 July 2020, Virtual Event. Proceedings of Machine Learning Research, vol. 119, pp. 345–355. PMLR (2020). http://proceedings.mlr.press/v119/antoniadis20a.html

  2. Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, Virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/5a378f8490c8d6af8647a753812f6e31-Abstract.html

  3. Azar, Y., Leonardi, S., Touitou, N.: Flow time scheduling with uncertain processing time. In: Khuller, S., Williams, V.V. (eds.) STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, 21–25 June 2021, pp. 1070–1080. ACM (2021). https://doi.org/10.1145/3406325.3451023

  4. Bamas, É., Maggiori, A., Rohwedder, L., Svensson, O.: Learning augmented energy minimization via speed scaling. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, Virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/af94ed0d6f5acc95f97170e3685f16c0-Abstract.html

  5. Bamas, É., Maggiori, A., Svensson, O.: The primal-dual method for learning augmented algorithms. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, Virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/e834cb114d33f729dbc9c7fb0c6bb607-Abstract.html

  6. Banerjee, S.: Improving online rent-or-buy algorithms with sequential decision making and ML predictions. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, Virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/f12a6a7477077af66212ef0813bcf332-Abstract.html

  7. Bar-Noy, A., Schieber, B.: The Canadian Traveller problem. In: Aggarwal, A. (ed.) Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 28–30 January 1991, San Francisco, California, USA, pp. 261–270. ACM/SIAM (1991). http://dl.acm.org/citation.cfm?id=127787.127835

  8. 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 (2013). https://doi.org/10.1007/s10878-013-9634-8

    Article  MathSciNet  MATH  Google Scholar 

  9. Bergé, P., Hemery, J., Rimmel, A., Tomasik, J.: On the competitiveness of memoryless strategies for the \(k\)-Canadian Traveller Problem. In: International Conference Combinatorial Optimization and Applications (COCOA), Atlanta, United States, December 2018. https://hal.archives-ouvertes.fr/hal-02022459

  10. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)

    Google Scholar 

  11. Cole, R., Roughgarden, T.: The sample complexity of revenue maximization. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May–03 June 2014, pp. 243–252. ACM (2014). https://doi.org/10.1145/2591796.2591867

  12. Demaine, E.D., Huang, Y., Liao, C.-S., Sadakane, K.: Approximating the Canadian Traveller problem with online randomization. Algorithmica 83(5), 1524–1543 (2021). https://doi.org/10.1007/s00453-020-00792-6

    Article  MathSciNet  MATH  Google Scholar 

  13. Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Chuang, J., Fortnow, L., Pu, P. (eds.) Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, 6–10 July 2009, pp. 71–78. ACM (2009). https://doi.org/10.1145/1566374.1566384

  14. Ergun, J.C., Feng, Z., Silwal, S., Woodruff, D.P., Zhou, S.: Learning-augmented \(k\)-means clustering (2021). https://doi.org/10.48550/ARXIV.2110.14094. https://arxiv.org/abs/2110.14094

  15. Gollapudi, S., Panigrahi, D.: Online algorithms for rent-or-buy with expert advice. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9–15 June 2019, Long Beach, California, USA. Proceedings of Machine Learning Research, vol. 97, pp. 2319–2327. PMLR (2019). http://proceedings.mlr.press/v97/gollapudi19a.html

  16. Huang, Y., Liao, C.-S.: The Canadian Traveller problem revisited. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 352–361. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35261-4_38

    Chapter  Google Scholar 

  17. Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Non-clairvoyant scheduling with predictions. In: Agrawal, K., Azar, Y. (eds.) SPAA 2021: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6–8 July 2021, pp. 285–294. ACM (2021). https://doi.org/10.1145/3409964.3461790

  18. Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5–8 January 2020, pp. 1859–1877. SIAM (2020). https://doi.org/10.1137/1.9781611975994.114

  19. Lavastida, T., Moseley, B., Ravi, R., Xu, C.: Learnable and instance-robust predictions for online matching, flows and load balancing. In: Mutzel, P., Pagh, R., Herman, G. (eds.) 29th Annual European Symposium on Algorithms, ESA 2021, 6–8 September 2021, Lisbon, Portugal (Virtual Conference). LIPIcs, vol. 204, pp. 59:1–59:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.ESA.2021.59

  20. Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt Rinehart and Winston, New York (1977)

    Google Scholar 

  21. Lindermayr, A., Megow, N., Simon, B.: Double coverage with machine-learned advice. In: Braverman, M. (ed.) 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, 31 January–3 February 2022, Berkeley, CA, USA. LIPIcs, vol. 215, pp. 99:1–99:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ITCS.2022.99

  22. Lu, P., Ren, X., Sun, E., Zhang, Y.: Generalized sorting with predictions. In: Le, H.V., King, V. (eds.) 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, 11–12 January 2021, pp. 111–117. SIAM (2021). https://doi.org/10.1137/1.9781611976496.13

  23. Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Dy, J.G., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, 10–15 July 2018. Proceedings of Machine Learning Research, vol. 80, pp. 3302–3311. PMLR (2018). http://proceedings.mlr.press/v80/lykouris18a.html

  24. Medina, A.M., Vassilvitskii, S.: Revenue optimization with approximate bid predictions. CoRR abs/1706.04732 (2017). http://arxiv.org/abs/1706.04732

  25. Mitzenmacher, M.: Scheduling with predictions and the price of misprediction. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, 12–14 January 2020, Seattle, Washington, USA. LIPIcs, vol. 151, pp. 14:1–14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.14

  26. Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 646–662. Cambridge University Press, Cambridge (2020). https://doi.org/10.1017/9781108637435.037

  27. Nikolova, E., Karger, D.R.: Route planning under uncertainty: the Canadian Traveller problem. In: Fox, D., Gomes, C.P. (eds.) Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, 13–17 July 2008, pp. 969–974. AAAI Press (2008). http://www.aaai.org/Library/AAAI/2008/aaai08-154.php

  28. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Hoboken (1982)

    MATH  Google Scholar 

  29. Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127–150 (1991). https://doi.org/10.1016/0304-3975(91)90263-2

    Article  MathSciNet  MATH  Google Scholar 

  30. Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: NeurIPS, Montréal, Canada, pp. 9684–9693 (2018). https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html

  31. Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5–8 January 2020, pp. 1834–1845. SIAM (2020). https://doi.org/10.1137/1.9781611975994.112

  32. Shiri, D., Salman, F.S.: On the randomized online strategies for the k-Canadian traveler problem. J. Comb. Optim. 38, 254–267 (2019)

    Article  MathSciNet  Google Scholar 

  33. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985). https://doi.org/10.1145/2786.2793

    Article  MathSciNet  Google Scholar 

  34. Vee, E., Vassilvitskii, S., Shanmugasundaram, J.: Optimal online assignment with forecasts. In: Parkes, D.C., Dellarocas, C., Tennenholtz, M. (eds.) Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, 7–11 June 2010, pp. 109–118. ACM (2010). https://doi.org/10.1145/1807342.1807360

  35. Wang, S., Li, J., Wang, S.: Online algorithms for multi-shop ski rental with machine learned advice. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, Virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/5cc4bb753030a3d804351b2dfec0d8b5-Abstract.html

  36. Wei, A.: Better and simpler learning-augmented online caching. In: Byrka, J., Meka, R. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 176, pp. 60:1–60:17. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.60. https://drops.dagstuhl.de/opus/volltexte/2020/12663

  37. Wei, A., Zhang, F.: Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, Virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/5bd844f11fa520d54fa5edec06ea2507-Abstract.html

  38. Westphal, S.: A note on the k-Canadian Traveller problem. Inf. Process. Lett. 106(3), 87–89 (2008). https://www.sciencedirect.com/science/article/pii/S0020019007002876

  39. 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). https://doi.org/10.1007/s10878-008-9156-y

    Article  MathSciNet  MATH  Google Scholar 

  40. Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity. In: 18th Annual Symposium on Foundations of Computer Science (SFCS 1977), pp. 222–227 (1977)

    Google Scholar 

Download references

Acknowledgements

This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

Author information

Authors and Affiliations

  1. Sorbonne Université, CNRS, LIP6, 75005, Paris, France

    Evripidis Bampis, Bruno Escoffier & Michalis Xefteris

  2. Institut Universitaire de France, Paris, France

    Bruno Escoffier

Authors
  1. Evripidis Bampis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bruno Escoffier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michalis Xefteris
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michalis Xefteris .

Editor information

Editors and Affiliations

  1. Aalto University, Espoo, Finland

    Parinya Chalermsook

  2. Shanghai University of Finance and Economics, Shanghai, China

    Bundit Laekhanukit

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bampis, E., Escoffier, B., Xefteris, M. (2022). Canadian Traveller Problem with Predictions. In: Chalermsook, P., Laekhanukit, B. (eds) Approximation and Online Algorithms. WAOA 2022. Lecture Notes in Computer Science, vol 13538. Springer, Cham. https://doi.org/10.1007/978-3-031-18367-6_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-18367-6_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-18366-9

  • Online ISBN: 978-3-031-18367-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation