Document Open Access Logo

The Expanding Search Ratio of a Graph

Authors Spyros Angelopoulos, Christoph Dürr, Thomas Lidbetter

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.9.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Spyros Angelopoulos
Christoph Dürr
Thomas Lidbetter

Cite As Get BibTex

Spyros Angelopoulos, Christoph Dürr, and Thomas Lidbetter. The Expanding Search Ratio of a Graph. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.9

Abstract

We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. Most of the previous work on this problem considers the pathwise cost formulation, in which the cost incurred by the searcher is the overall time to locate the target, assuming that the searcher moves at unit speed. More recent work introduced the setting of expanding search in which the searcher incurs cost only upon visiting previously unexplored areas of the graph. Such a paradigm is useful in modeling problems in which the cost of re-exploration is negligible (such as coal mining).

In our work we study algorithmic and computational issues of expanding search, for a variety of search environments including general graphs, trees and star-like graphs. In particular, we rely on the deterministic and randomized search ratio as the performance measures of search strategies, which were originally introduced by Koutsoupias and Papadimitriou [ICALP 1996] in the context of pathwise search. The search ratio is essentially the best competitive ratio among all possible strategies. Our main objective is to explore how the transition from pathwise to expanding search affects the competitive analysis, which has applications to optimization problems beyond the strict boundaries of search problems.

Subject Classification

Keywords
  • Search games
  • randomized algorithms
  • competitive analysis
  • game theory

Metrics

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

References

  1. S. Alpern, V. Baston, and S. Gal. Network search games with immobile hider, without a designated searcher starting point. International Journal of Game Theory, 37(2):281-302, 2008. Google Scholar
  2. S. Alpern, R. Fokkink, L. Ga̧sieniec, R. Lindelauf, and V. S. Subrahmanian, editors. Search theory. A game theoretic perspective. New York, NY: Springer, 2013. Google Scholar
  3. S. Alpern and S. Gal. A mixed strategy minimax theorem without compactness. SIAM Journal on Control and Optimization, 26(6):1357-1361, 1988. Google Scholar
  4. S. Alpern and S. Gal. The theory of search games and rendezvous. Kluwer Academic Publishers, 2003. Google Scholar
  5. S. Alpern and T. Lidbetter. Mining coal or finding terrorists: The expanding search paradigm. Operations Research, 61(2):265-279, 2013. Google Scholar
  6. S. Angelopoulos. Further connections between contract-scheduling and ray-searching problems. In Proc. of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 1516-1522, 2015. Google Scholar
  7. S. Angelopoulos, A. López-Ortiz, and K. Panagiotou. Multi-target ray searching problems. Theoretical Computer Science, 540:2-12, 2014. Google Scholar
  8. G. Ausiello, S. Leonardi, and A. Marchetti-Spaccamela. On salesmen, repairmen, spiders, and other traveling agents. In Algorithms and Complexity, 4th Italian Conference, CIAC 2000, Rome, Italy, March 2000, Proceedings, pages 1-16, 2000. URL: http://dx.doi.org/10.1007/3-540-46521-9_1,
  9. R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Cmputation, 106:234-244, 1993. Google Scholar
  10. V. Baston and K. Kikuta. Search games on networks with travelling and search costs and with arbitrary searcher starting points. Networks, 62(1):72-79, 2013. Google Scholar
  11. V. Baston and K. Kikuta. Search games on a network with travelling and search costs. International Journal of Game Theory, 44(2):347-365, 2015. Google Scholar
  12. A. Beck. On the linear search problem. Naval Research Logistics, 2:221-228, 1964. Google Scholar
  13. R. Bellman. An optimal search problem. SIAM Review, 5:274, 1963. Google Scholar
  14. D.S. Bernstein, T. J. Perkins, S. Zilberstein, and L. Finkelstein. Scheduling contract algorithms on multiple processors. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI), pages 702-706, 2002. Google Scholar
  15. P. Bose, J. De Carufel, and S. Durocher. Searching on a line: A complete characterization of the optimal solution. Theoretical Computer Science, 569:24-42, 2015. Google Scholar
  16. A. Dagan and S. Gal. Network search games, with arbitrary searcher starting point. Networks, 52(3):156-161, 2008. Google Scholar
  17. E.D. Demaine, S.P. Fekete, and S. Gal. Online searching with turn cost. Theoretical Computer Science, 361:342-355, 2006. Google Scholar
  18. R. Fleischer, T. Kamphans, R. Klein, E. Langetepe, and G. Trippen. Competitive online approximation of the optimal search ratio. SIAM Journal on Computing, 38(3):881-898, 2008. Google Scholar
  19. S. Gal. A general search game. Israel Journal of Mathematics, 12:32-45, 1972. Google Scholar
  20. S. Gal. Minimax solutions for linear search problems. SIAM J. on Applied Math., 27:17-30, 1974. Google Scholar
  21. S. Gal. Search games with mobile and immobile hider. SIAM Journal on Control and Optimization, 17(1):99-122, 1979. Google Scholar
  22. S. Gal. Search Games. Academic Press, 1980. Google Scholar
  23. S. Gal. On the optimality of a simple strategy for searching graphs. International Journal of Game Theory, 29(4):533-542, 2001. Google Scholar
  24. P. Jaillet and M. Stafford. Online searching. Operations Research, 49:234-244, 1993. Google Scholar
  25. M-Y. Kao and M.L. Littman. Algorithms for informed cows. In Proceedings of the AAAI 1997 Workshop on Online Search, 1997. Google Scholar
  26. M-Y. Kao, Y. Ma, M. Sipser, and Y.L. Yin. Optimal constructions of hybrid algorithms. Journal of Algorithms, 29(1):142-164, 1998. Google Scholar
  27. M-Y. Kao, J.H. Reif, and S.R. Tate. Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inform. and Comp., 131(1):63-80, 1996. Google Scholar
  28. D. G. Kirkpatrick. Hyperbolic dovetailing. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pages 616-627, 2009. Google Scholar
  29. E. Koutsoupias, C.H. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In Proc. of the 23rd Int. Colloq. on Automata, Languages and Programming (ICALP), pages 280-289, 1996. Google Scholar
  30. T. Lidbetter. Search games with multiple hidden objects. SIAM Journal on Control and Optimization, 51(4):3056-3074, 2013. Google Scholar
  31. A. López-Ortiz and S. Schuierer. The ultimate strategy to search on m rays? Theoretical Computer Science, 261(2):267-295, 2001. Google Scholar
  32. A. López-Ortiz and S. Schuierer. On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. Theor. Comp. Sci., 310(1-3):527-537, 2004. Google Scholar
  33. A. McGregor, K. Onak, and R. Panigrahy. The oil searching problem. In Proc. of the 17th European Symposium on Algorithms (ESA), pages 504-515, 2009. Google Scholar
  34. L. Pavlovic. A search game on the union of graphs with immobile hider. Naval Research Logistics, 42(8):1177-1199, 1995. Google Scholar
  35. J. Reijnierse and J. Potters. Search games with immobile hider. International Journal of Game Theory, 21:385-394, 1993. Google Scholar
  36. S. Schuierer. A lower bound for randomized searching on m rays. In Computer Science in Perspective, pages 264-277, 2003. 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 About DROPS Imprint Privacy Contact