Document Open Access Logo

Improved Approximation Algorithms for the Expanding Search Problem

Authors Svenja M. Griesbach , Felix Hommelsheim , Max Klimm , Kevin Schewior

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.54.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Svenja M. Griesbach
  • Institute for Mathematics, Technische Universität Berlin, Germany
Felix Hommelsheim
  • Faculty of Mathematics and Computer Science, Universität Bremen, Germany
Max Klimm
  • Institute for Mathematics, Technische Universität Berlin, Germany
Kevin Schewior
  • Department Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

Funding

  • Griesbach, Svenja M.: Supported by Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy, Berlin Mathematics Research Center (grant EXC-2046/1, Project 39068689) and HYPATIA.SCIENCE (Department of Mathematics and Computer Science, University of Cologne).
  • Klimm, Max: Supported by Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy, Berlin Mathematics Research Center (grant EXC-2046/1, Project 390685689).
  • Schewior, Kevin: Supported in part by the Independent Research Fund Denmark, Natural Sciences (grant DFF-0135-00018B).

Acknowledgements

We thank Spyros Angelopoulos for fruitful discussions and pointers to earlier literature.

Cite AsGet BibTex

Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior. Improved Approximation Algorithms for the Expanding Search Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.54

Abstract

A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a (2e+ε)-approximation for any ε > 0. For the case that all vertices have unit weight, we provide a 2e-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an 8-approximation was known.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation Algorithm
  • Expanding Search
  • Search Problem
  • Graph Exploration
  • Traveling Repairperson Problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Foto N. Afrati, Stavros S. Cosmadakis, Christos H. Papadimitriou, George Papageorgiou, and Nadia Papakostantinou. The complexity of the travelling repairman problem. RAIRO - Theoretical Informatics and Applications, 20(1):79-87, 1986. Google Scholar
  2. Steve Alpern, Robbert Fokkink, Leszek Gasieniec, Roy Lindelauf, and V. S. Subrahmanian. Search Theory. Springer, New York, 2013. Google Scholar
  3. Steve Alpern and Shmuel Gal. The Theory of Search Games and Rendezvous, volume 55 of International Series in Operations Research and Management Science. Kluwer, 2003. Google Scholar
  4. Steve Alpern and Thomas Lidbetter. Mining coal or finding terrorists: The expanding search paradigm. Operations Research, 61(2):265-279, 2013. URL: https://doi.org/10.1287/opre.1120.1134.
  5. Steve Alpern and Thomas Lidbetter. Approximate solutions for expanding search games on general networks. Annals of Opererations Research, 275(2):259-279, 2019. Google Scholar
  6. Spyros Angelopoulos, Christoph Dürr, and Thomas Lidbetter. The expanding search ratio of a graph. Discrete Applied Mathematics, 260:51-65, 2019. Google Scholar
  7. Aaron Archer and Anna Blasiak. Improved approximation algorithms for the minimum latency problem via prize-collecting strolls. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 429-447, 2010. Google Scholar
  8. Aaron Archer, Asaf Levin, and David P. Williamson. A faster, better approximation algorithm for the minimum latency problem. SIAM Journal on Computing, 37(5):1472-1498, 2008. Google Scholar
  9. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, 1998. Google Scholar
  10. Sanjeev Arora and George Karakostas. Approximation schemes for minimum latency problems. SIAM Journal on Computing, 32(5):1317-1337, 2003. Google Scholar
  11. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Google Scholar
  12. Igor Averbakh. Emergency path restoration problems. Discrete Optimization, 9(1):58-64, 2012. Google Scholar
  13. Igor Averbakh and Jordi Pereira. The flowtime network construction problem. IIE Transactions, 44(8):681-694, 2012. Google Scholar
  14. Marshall Bern and Paul Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4):171-176, 1989. Google Scholar
  15. Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. The minimum latency problem. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 163-171, 1994. Google Scholar
  16. Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. Paths, trees, and minimum latency tours. In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 36-45, 2003. Google Scholar
  17. Chandra Chekuri and Amit Kumar. Maximum coverage problem with group budget constraints and applications. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pages 72-83, 2004. Google Scholar
  18. Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, and Pieter Vansteenwegen. Heuristics for the traveling repairman problem with profits. Computers & Operations Research, 40:1700-1707, 2013. Google Scholar
  19. Jittat Fakcharoenphol, Chris Harrelson, and Satish Rao. The k-traveling repairmen problem. ACM Transactions on Algorithms, 3(4):40:1-40:16, 2007. Google Scholar
  20. Matteo Fischetti, Gilbert Laporte, and Silvano Martello. The delivery man problem and cumulative matroids. Operations Research, 41:1010-1176, 1993. Google Scholar
  21. Zachary Friggstad, Mohammad R. Salavatipour, and Zoya Svitkina. Asymmetric traveling salesman path and directed latency problems. SIAM Journal on Computing, 42:1596-1619, 2013. Google Scholar
  22. Shmuel Gal. Search games with mobile and immobile hider. SIAM Journal on Control and Optimization, 17:99-122, 1979. Google Scholar
  23. Shmuel Gal. Search Games. Academic Press, New York, 1980. Google Scholar
  24. Alfredo García, Pedro Jodrá, and Javier Tejel. A note on the travelling repairman problem. Networks, 40:27-31, 2002. Google Scholar
  25. Naveen Garg. Saving an epsilon: A 2-approximation for the k-MST problem in graphs. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 396-402, 2005. Google Scholar
  26. Michel X. Goemans and Jon M. Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111-124, 1998. Google Scholar
  27. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  28. Svenja M Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior. Improved approximation algorithms for the expanding search problem. arXiv preprint arXiv:2301.03638, 2023. Google Scholar
  29. Ben Hermans, Roel Leus, and Jannik Matuschke. Exact and approximation algorithms for the expanding search problem. INFORMS Journal on Computing, 34(1):281-296, 2022. Google Scholar
  30. Rufus Isaacs. Differential Games. John Wiley and Sons, New York, 1965. Google Scholar
  31. David S. Johnson, Maria Minkoff, and Steven Philipps. The prize collecting Steiner tree problem: Theory and practice. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 760-769, 2000. Google Scholar
  32. David Kirkpatrick. Hyperbolic dovetailing. In Proceedings of the Annual European Symposium on Algorithms (ESA), pages 516-527, 2009. Google Scholar
  33. Elias Koutsoupias, Christos H. Papadimitriou, and Mihalis Yannakakis. Searching a fixed graph. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), pages 280-289, 1996. Google Scholar
  34. Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, and Leen Stougie. News from the online traveling repairman. Theoretical Computer Science, 295:279-294, 2003. Google Scholar
  35. Songtao Li and Simin Huang. Multiple searchers searching for a randomly distributed immobile target on a unit network. Networks, 71(1):60-80, 2018. Google Scholar
  36. Edward Minieka. The delivery man problem on a tree network. Annals of Operations Research, 18:261-266, 1989. Google Scholar
  37. Viswanath Nagarajan and R. Ravi. The directed minimum latency problem. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pages 193-206. Springer, 2008. Google Scholar
  38. Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM, 23:555-565, 1976. Google Scholar
  39. René Sitters. The minimum latency problem is NP-hard for weighted trees. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 230-239, 2002. Google Scholar
  40. René Sitters. Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. SIAM Journal on Computing, 50(5):1580-1602, 2021. Google Scholar
  41. Yushi Tan, Feng Qiu, Arindam K. Das, Daniel S. Kirschen, Payman Arabshahi, and Jianhui Wang. Scheduling post-disaster repairs in electricity distribution networks. IEEE Trans. Power Syst., 34(4):2611-2621, 2019. Google Scholar
  42. K. E. Trummel and J. R. Weisinger. Technical note - The complexity of the optimal searcher path problem. Opererations Research, 34(2):324-327, 1986. Google Scholar
  43. John N. Tsitsiklis. Special cases of traveling salesman and repairman problems with time windows. Networks, 22:262-283, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact