Document Open Access Logo

Online Search with a Hint

Author Spyros Angelopoulos

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.51.pdf
  • Filesize: 472 kB
  • 16 pages

Document Identifiers

Author Details

Spyros Angelopoulos
  • Sorbonne Université, CNRS, Laboratoire d’informatique de Paris 6, LIP6, 75252 Paris, France

Funding

  • Angelopoulos, Spyros: Research benefited from the support of the FMJH Program PGMO and from the support to this program from EDF-THALES-ORANGE. Also partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

Acknowledgements

I am thankful to Thomas Lidbetter for his comments on an early version of this paper.

Cite As Get BibTex

Spyros Angelopoulos. Online Search with a Hint. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.51

Abstract

The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search. 
In this work we study this problem in a setting in which the searcher has a hint concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searcher’s performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Search problems
  • searching on the line
  • competitive analysis
  • predictions

Metrics

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

Related Versions

References

  1. Steve Alpern and Shmuel Gal. The theory of search games and rendezvous. Kluwer Academic Publishers, 2003. Google Scholar
  2. Spyros Angelopoulos. Further connections between contract-scheduling and ray-searching problems. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 1516-1522, 2015. Google Scholar
  3. Spyros Angelopoulos, Diogo Arsénio, and Christoph Dürr. Infinite linear programming and online searching with turn cost. Theoretical Computer Science, 670:11-22, 2017. Google Scholar
  4. Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Best-of-two-worlds analysis of online search. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 7:1-7:17, 2019. Google Scholar
  5. Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, pages 52:1-52:15, 2020. 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. Spyros Angelopoulos and Shahin Kamali. Contract scheduling with predictions, 2020. Avaliable as URL: https://arxiv.org/abs/2011.12439.
  8. Yossi Azar, Andrei Z. Broder, and Mark S. Manasse. On-line choice of on-line algorithms. In Vijaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 432-440. ACM/SIAM, 1993. Google Scholar
  9. Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory G.E. Rawlins. Searching in the plane. Information and Computation, 106:234-244, 1993. Google Scholar
  10. Anatole Beck. On the linear search problem. Naval Research Logistics, 2:221-228, 1964. Google Scholar
  11. Anatole Beck. More on the linear search problem. Israel Journal of Mathematics, 3(2):61-70, 1965. Google Scholar
  12. Anatole Beck and Micah Beck. Son of the linear search problem. Israel Journal of Mathematics, 48(2-3):109-122, 1984. Google Scholar
  13. Anatole Beck and Micah Beck. The linear search problem rides again. Israel Journal of Mathematics, 53(3):365-372, 1986. Google Scholar
  14. Anatole Beck and Micah Beck. The revenge of the linear search problem. SIAM journal on control and optimization, 30(1):112-122, 1992. Google Scholar
  15. Anatole Beck and D.J. Newman. Yet more on the linear search problem. Israel Journal of Mathematics, 8:419-429, 1970. Google Scholar
  16. Anatole Beck and Peter Warren. The return of the linear search problem. Israel Journal of Mathematics, 14(2):169-183, 1973. Google Scholar
  17. R. Bellman. An optimal search problem. SIAM Review, 5:274, 1963. Google Scholar
  18. Daniel S. Bernstein, Lev Finkelstein, and Shlomo Zilberstein. Contract algorithms and robots on rays: unifying two scheduling problems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pages 1211-1217, 2003. Google Scholar
  19. Daniel S. Bernstein, Theodore J. Perkins, Shlomo Zilberstein, and Lev Finkelstein. Scheduling contract algorithms on multiple processors. In Proceedings of the Eighteenth AAAI Conference on Artificial Intelligence (AAAI), pages 702-706, 2002. Google Scholar
  20. Prosenjit Bose, Jean-Lou De Carufel, and Stephane Durocher. Searching on a line: A complete characterization of the optimal solution. Theoretical Computer Science, 569:24-42, 2015. Google Scholar
  21. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. SIGACT News, 47(3):93-129, 2016. Google Scholar
  22. Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil M. Shende. Search on a line by byzantine robots. In 27th International Symposium on Algorithms and Computation, ISAAC, volume 64 of LIPIcs, pages 27:1-27:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  23. Erik D. Demaine, Sándor Fekete, and Shmuel Gal. Online searching with turn cost. Theoretical Computer Science, 361:342-355, 2006. Google Scholar
  24. Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive online approximation of the optimal search ratio. SIAM Journal on Computing, 38(3):881-898, 2008. Google Scholar
  25. Shmuel Gal. A general search game. Israel Journal of Mathematics, 12:32-45, 1972. Google Scholar
  26. Shmuel Gal. Minimax solutions for linear search problems. SIAM Journal on Applied Mathematics, 27:17-30, 1974. Google Scholar
  27. Patrick Jaillet and Matthew Stafford. Online searching. Operations Research, 49:234-244, 1993. Google Scholar
  28. Ming-Yang Kao and Michael Littman. Algorithms for informed cows. In Proceedings of the AAAI 1997 Workshop on Online Search, 1997. Google Scholar
  29. Ming-Yang Kao, Yuan Ma, Michael Sipser, and Yiqun Yin. Optimal constructions of hybrid algorithms. Journal of Algorithms, 29(1):142-164, 1998. Google Scholar
  30. Ming-Yang Kao, John H Reif, and Stephen R Tate. Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Information and Computation, 131(1):63-80, 1996. Google Scholar
  31. David G. Kirkpatrick. Hyperbolic dovetailing. In Proceedings of the 17th European Symposium on Algorithms (ESA), pages 616-627, 2009. Google Scholar
  32. Elias Koutsoupias, Christos H. Papadimitriou, and Michalis Yannakakis. Searching a fixed graph. In Proc. of the 23rd Int. Colloq. on Automata, Languages and Programming (ICALP), pages 280-289, 1996. Google Scholar
  33. Andrey Kupavskii and Emo Welzl. Lower bounds for searching robots, some faulty. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 447-453, 2018. Google Scholar
  34. Alejandro López-Ortiz and Sven Schuierer. The ultimate strategy to search on m rays? Theoretical Computer Science, 261(2):267-295, 2001. Google Scholar
  35. Alejandro López-Ortiz and Sven Schuierer. On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. Theoretical Computer Science, 310(1-3):527-537, 2004. Google Scholar
  36. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning, ICML, pages 3302-3311, 2018. Google Scholar
  37. Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems 30, pages 5788-5799. Curran Associates, Inc., 2017. Google Scholar
  38. Andrew McGregor, Krzysztof Onak, and Rina Panigrahy. The oil searching problem. In Proceedings of the 17th European Symposium on Algorithms (ESA), pages 504-515, 2009. Google Scholar
  39. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, volume 31, pages 9661-9670, 2018. Google Scholar
  40. Sven Schuierer. Lower bounds in online geometric searching. Computational Geometry: Theory and Applications, 18(1):37-53, 2001. Google Scholar
  41. Sven 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