Search Games with Predictions

References

• Almanza M, Chierichetti F, Lattanzi S, Panconesi A, Re G (2021) Online facility location with multiple advice. Adv. Neural Inform. Processing Systems 34:4661–4673.Google Scholar
• Alpern S (2023) The faulty satnav (GPS) problem: Search for home in networks with unreliable directions. Theoret. Comput. Sci. 975:114109.Crossref, Google Scholar
• Alpern S, Gal S (2003) The Theory of Search Games and Rendezvous (Kluwer Academic Publishers, Dordrecht, Netherlands).Google Scholar
• Alpern S, Lidbetter T (2013) Mining coal or finding terrorists: The expanding search paradigm. Oper. Res. 61(2):265–279.Link, Google Scholar
• Alpern S, Lidbetter T (2024) Search for an immobile hider on a binary tree with unreliable locational information. Oper. Res. 73(2):583–594.Link, Google Scholar
• Alpern S, Morton A, Papadaki K (2011) Patrolling games. Oper. Res. 59(5):1246–1257.Link, Google Scholar
• Alpern S, Fokkink R, Gasieniec L, Lindelauf R, Subrahmanian V (2013) Search Theory: A Game Theoretic Perspective (Springer, Berlin).Crossref, Google Scholar
• Anand K, Ge R, Kumar A, Panigrahi D (2022) Online algorithms with multiple predictions. Proc. Machine Learn. Res. 162:582–598.Google Scholar
• Angelopoulos S (2022) Further connections between contract-scheduling and ray-searching problems. J. Scheduling 25(2):139–155.Crossref, Google Scholar
• Angelopoulos S (2023a) Competitive search in the line and the star with predictions. Leroux J, Lombardy S, Peleg D, eds. 48th Internat. Sympos. Math. Foundations Comput. Sci. (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 12:1–12:15.Google Scholar
• Angelopoulos S (2023b) Online search with a hint. Inform. Comput. 295(Part B):105091.Crossref, Google Scholar
• Antoniadis A, Coester C, Eliáš M, Polak A, Simon B (2023) Online metric algorithms with untrusted predictions. ACM Trans. Algorithms 19(2):1–34.Crossref, Google Scholar
• Azar Y, Panigrahi D, Touitou N (2022) Online graph algorithms with predictions. Naor J, Buchbinder N, eds. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 35–66.Google Scholar
• Baeza-Yates RA, Culberson JC, Rawlins GG (1993) Searching in the plane. Inform. Comput. 106(2):234–244.Crossref, Google Scholar
• Bamas E, Maggiori A, Svensson O (2020) The primal-dual method for learning augmented algorithms. Adv. Neural Inform. Processing Systems 33:20083–20094.Google Scholar
• Banerjee S, Cohen-Addad V, Gupta A, Li Z (2023) Graph searching with predictions. Kalai YT, ed. 14th Innovations Theoret. Comput. Sci. Conf. (ITCS 2023) (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 12:1–12:24.Google Scholar
• Baston V, Gal S (2001) Rendezvous search when marks are left at the starting points. Naval Res. Logist. 48(8):722–731.Crossref, Google Scholar
• Beck A, Newman D (1970) Yet more on the linear search problem. Israel J. Math. 8:419–429.Crossref, Google Scholar
• Bernstein DS, Finkelstein L, Zilberstein S (2003) Contract algorithms and robots on rays: Unifying two scheduling problems. Proc. 18th Internat. Joint Conf. Artificial Intelligence (IJCAI), 1211–1217.Google Scholar
• Black WL (1965) Discrete sequential search. Inform. Control 8(2):159–162.Crossref, Google Scholar
• Boczkowski L, Korman A, Rodeh Y (2018) Searching a tree with permanently noisy advice. Azar Y, Bast H, Herman G, eds. 26th Annual Eur. Sympos. Algorithms (ESA 2018) (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 1–32.Google Scholar
• Bonato A, Georgiou K, MacRury C, Pralat P (2023) Algorithms for p-faulty search on a half-line. Algorithmica 85(8):2485–2514.Crossref, Google Scholar
• Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Boyd SP, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bui T, Lidbetter T, Lin KY (2024) Optimal pure strategies for a discrete search game. Eur. J. Oper. Res. 313(2):767–775.Crossref, Google Scholar
• Cabello S, Giannopoulos P (2024) Searching in Euclidean spaces with predictions. Preprint, submitted August 9, https://arxiv.org/abs/2408.04964v1.Google Scholar
• Christianson N, Shen J, Wierman A (2023) Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. Proc. Machine Learn. Res. 206:9377–9399.Google Scholar
• Clarkson J, Lin KY (2024) Computing optimal strategies for a search game in discrete locations. INFORMS J. Comput. 37(3):666–683.Link, Google Scholar
• Clarkson J, Lin KY, Glazebrook KD (2023) A classical search game in discrete locations. Math. Oper. Res. 48(2):687–707.Link, Google Scholar
• Coleman J, Kranakis E, Krizanc D, Morales-Ponce O (2023) Line search for an oblivious moving target. Hillel E, Palmieri R, Rivière E, eds. 26th Internat. Conf. Principles Distributed Systems (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 12:1–12:19.Google Scholar
• Condon A, Deshpande A, Hellerstein L, Wu N (2009) Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Trans. Algorithms 5(2):24:1–24:34.Crossref, Google Scholar
• Demaine ED, Fekete S, Gal S (2006) Online searching with turn cost. Theoret. Comput. Sci. 361(2–3):342–355.Crossref, Google Scholar
• DePavia AF, Tani E, Vakilian A (2024) Learning-based algorithms for graph searching problems. Proc. Machine Learn. Res. 238:928–936.Google Scholar
• Diakonikolas I, Kontonis V, Tzamos C, Vakilian A, Zarifis N (2021) Learning online algorithms with distributional advice. Proc. Machine Learn. Res. 139:2687–2696.Google Scholar
• Dobrev S, Královič R, Markou E (2012) Online graph exploration with advice. Even G, Halldórsson MM, eds. Structural Inform. Comm. Complexity SIROCCO 2012 (Springer, Berlin), 267–278.Google Scholar
• Dütting P, Lattanzi S, Paes Leme R, Vassilvitskii S (2024) Secretaries with advice. Math. Oper. Res. 49(2):856–879.Link, Google Scholar
• Duvocelle B, Flesch J, Staudigl M, Vermeulen D (2022) A competitive search game with a moving target. Eur. J. Oper. Res. 303(2):945–957.Crossref, Google Scholar
• Eberle F, Lindermayr A, Megow N, Nölke L, Schlöter J (2022) Robustification of online graph exploration methods. Proc. AAAI Conf. Artificial Intelligence 36(9):9732–9740.Crossref, Google Scholar
• Fiat A, Karp RM, Luby M, McGeoch LA, Sleator DD, Young NE (1991) Competitive paging algorithms. J. Algorithms 12(4):685–699.Crossref, Google Scholar
• Gal S (1980) Search Games (Academic Press, New York).Google Scholar
• Gollapudi S, Panigrahi D (2019) Online algorithms for rent-or-buy with expert advice. Proc. Machine Learn. Res. 97:2319–2327.Google Scholar
• Gomes CP, Selman B (2001) Algorithm portfolios. Artificial Intelligence 126(1–2):43–62.Crossref, Google Scholar
• Gorain B, Pelc A (2018) Deterministic graph exploration with advice. ACM Trans. Algorithms 15(1):1–17.Crossref, Google Scholar
• Im S, Kumar R, Montazer Qaem M, Purohit M (2021) Online knapsack with frequency predictions. Adv. Neural Inform. Processing Systems 34:2733–2743.Google Scholar
• Isaacs R (1965) Differential Games (Wiley, New York).Google Scholar
• Jaillet P, Stafford M (2001) Online searching. Oper. Res. 49(4):501–515.Link, Google Scholar
• Kadioglu S, Malitsky Y, Sellmann M, Tierney K (2010) ISAC–Instance-Specific Algorithm Configuration. Coelho H, Studer R, Wooldridge M, eds. Proc. 2010 Conf. ECAI 2010 19th Eur. Conf. Artificial Intelligence (IOS Press, Amsterdam), 751–756.Google Scholar
• Kalyanasundaram B, Pruhs K (1993) A competitive analysis of algorithms for searching unknown scenes. Comput. Geometry 3(3):139–155.Crossref, Google Scholar
• Kao MY, Reif JH, Tate SR (1996) Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inform. Comput. 131(1):63–80.Crossref, Google Scholar
• Kao MY, Ma Y, Sipser M, Yin Y (1998) Optimal constructions of hybrid algorithms. J. Algorithms 29(1):142–164.Crossref, Google Scholar
• Komm D, Královič R, Královič R, Smula J (2015) Treasure hunt with advice. Scheideler C, ed. Structural Inform. Comm. Complexity SIROCCO 2015 (Springer, Cham, Switzerland), 328–341.Google Scholar
• Koopman BO (1946) Search and screening. Technical Report No. 56, Operations Evaluation Group, Center for Naval Analysis, Rosslyn, VA.Google Scholar
• Koutsoupias E, Papadimitriou CH, Yannakakis M (1996) Searching a fixed graph. Meyer F, Monien B, eds. Automata Languages Programming ICALP 1996 (Springer, Berlin), 280–289.Google Scholar
• Kupavskii A, Welzl E (2018) Lower bounds for searching robots, some faulty. Newport C, Keidar I, eds. Proc. 2018 ACM Sympos. Principles Distributed Comput. (Association for Computing Machinery, New York), 447–453.Google Scholar
• Langetepe E (2010) On the optimality of spiral search. Charikar M, ed. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1–12.Google Scholar
• Lattanzi S, Lavastida T, Moseley B, Vassilvitskii S (2020) Online scheduling via learned weights. Chawla S, ed. Proc. 31st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1859–1877.Google Scholar
• Lee R, Sun B, Hajiesmaili M, Lui JCS (2024) Online search with predictions: Pareto-optimal algorithm and its applications in energy markets. E-Energy ‘24 15th ACM Internat. Conf. Future Sustainable Energy Systems (Association for Computing Machinery, New York), 50–71.Google Scholar
• Lidbetter T (2013) Search games with multiple hidden objects. SIAM J. Control Optim. 51(4):3056–3074.Crossref, Google Scholar
• Lin H, Luo T, Woodruff D (2022) Learning augmented binary search trees. Proc. Machine Learn. Res. 162:13431–13440.Google Scholar
• Lindermayr A, Megow N (2022) Repository of works on algorithms with predictions. Accessed August 25, 2025, https://algorithms-with-predictions.github.io/about.Google Scholar
• López-Ortiz A, Schuierer S (2001) The ultimate strategy to search on m rays? Theoret. Comput. Sci. 261(2):267–295.Crossref, Google Scholar
• López-Ortiz A, Schuierer S (2004) On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. Theoret. Comput. Sci. 310(1–3):527–537.Crossref, Google Scholar
• Lykouris T, Vassilvitskii S (2021) Competitive caching with machine learned advice. J. ACM 68(4):24:1–24:25.Crossref, Google Scholar
• Matula D (1964) A periodic optimal search. Amer. Math. Monthly 71(1):15–21.Crossref, Google Scholar
• Pelc A, Yadav RN (2021) Advice complexity of treasure hunt in geometric terrains. Inform. Comput. 281:104705.Crossref, Google Scholar
• Ruckle WH (1991) A discrete search game. Raghavan TES, Ferguson TS, Parthasarathy T, Vrieze OJ, eds. Stochastic Games and Related Topics. Theory and Decision Library, vol. 7 (Springer, Dordrecht, Netherlands), 29–43.Crossref, Google Scholar
• Smith WE (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1–2):59–66.Crossref, Google Scholar
• Sun B, Lee R, Hajiesmaili M, Wierman A, Tsang D (2021) Pareto-optimal learning-augmented algorithms for online conversion problems. Adv. Neural Inform. Processing Systems 34:10339–10350.Google Scholar
• Washburn A, Wood K (1995) Two-person zero-sum games for network interdiction. Oper. Res. 43(2):243–251.Link, Google Scholar
• Wei A, Zhang F (2020) Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Adv. Neural Inform Processing Systems 33:8042–8053.Google Scholar
• Xu L, Hutter F, Hoos HH, Leyton-Brown K (2008) SATzilla: Portfolio-based algorithm selection for SAT. J. Artificial Intelligence Res. 32:565–606.Crossref, Google Scholar