{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:07Z","timestamp":1740109327036,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:00:00Z","timestamp":1693008000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:00:00Z","timestamp":1693008000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100007493","name":"Fondation Math\u251c\u2310matique Jacques Hadamard","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007493","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0016"],"award-info":[{"award-number":["ANR-19-CE48-0016"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00453-023-01165-5","type":"journal-article","created":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T04:01:15Z","timestamp":1693022475000},"page":"3766-3792","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Best-of-Both-Worlds Analysis of Online Search"],"prefix":"10.1007","volume":"85","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shendan","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,26]]},"reference":[{"key":"1165_CR1","volume-title":"The Theory of Search Games and Rendezvous","author":"S Alpern","year":"2003","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, Berlin (2003)"},{"key":"1165_CR2","first-page":"1","volume":"5","author":"S Angelopoulos","year":"2016","unstructured":"Angelopoulos, S., Ars\u00e9nio, D., D\u00fcrr, C., L\u00f3pez-Ortiz, A.: Multi-processor search and scheduling problems with setup cost. Theory Comput. Syst. 5, 1\u201334 (2016)","journal-title":"Theory Comput. Syst."},{"key":"1165_CR3","unstructured":"Angelopoulos. S.: Further connections between contract-scheduling and ray-searching problems. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1516\u20131522, (2015)"},{"key":"1165_CR4","unstructured":"Angelopoulos, S.: Online search with a hint. In: Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), pp. 51:1\u201351:16 (2021)"},{"key":"1165_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2017.01.013","volume":"670","author":"S Angelopoulos","year":"2017","unstructured":"Angelopoulos, S., Ars\u00e9nio, D., D\u00fcrr, C.: Infinite linear programming and online searching with turn cost. Theoret. Comput. Sci. 670, 11\u201322 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"1165_CR6","unstructured":"Angelopoulos, S., Ars\u00e9nio, D., Kamali, S.: Competitive sequencing with noisy advice. arXiv:2111.05281 (2021)"},{"key":"1165_CR7","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: On the separation and equivalence of paging strategies. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 229\u2013237 (2007)"},{"issue":"5","key":"1165_CR8","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1007\/s00453-019-00638-w","volume":"82","author":"S Angelopoulos","year":"2020","unstructured":"Angelopoulos, S., Renault, M.P., Schweitzer, P.: Stochastic dominance and the bijective ratio of online algorithms. Algorithmica 82(5), 1101\u20131135 (2020)","journal-title":"Algorithmica"},{"issue":"2","key":"1165_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/2450142.2450143","volume":"60","author":"S Angelopoulos","year":"2013","unstructured":"Angelopoulos, S., Schweitzer, P.: Paging and list update under bijective analysis. J. ACM 60(2), 71\u2013718 (2013)","journal-title":"J. ACM"},{"key":"1165_CR10","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R., Culberson, J., Rawlins, G.: Searching in the plane. Inf. Comput. 106, 234\u2013244 (1993)","journal-title":"Inf. Comput."},{"key":"1165_CR11","first-page":"221","volume":"2","author":"A Beck","year":"1964","unstructured":"Beck, A.: On the linear search problem. Nav. Res. Logist. 2, 221\u2013228 (1964)","journal-title":"Nav. Res. Logist."},{"issue":"4","key":"1165_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"A Beck","year":"1970","unstructured":"Beck, A., Newman, D.J.: Yet more on the linear search problem. Israel J. Math. 8(4), 419\u2013429 (1970)","journal-title":"Israel J. Math."},{"key":"1165_CR13","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R.: An optimal search problem. SIAM Rev. 5, 274 (1963)","journal-title":"SIAM Rev."},{"key":"1165_CR14","doi-asserted-by":"crossref","unstructured":"Berman, P.: Online Algorithms: The State of the Art, chapter Online searching and navigation, pp. 232\u2013241. Springer (1998)","DOI":"10.1007\/BFb0029571"},{"key":"1165_CR15","unstructured":"Bernstein, D.S., Finkelstein, L., Zilberstein, S.: Contract algorithms and robots on rays: unifying two scheduling problems. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1211\u20131217 (2003)"},{"key":"1165_CR16","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.tcs.2014.12.007","volume":"569","author":"P Bose","year":"2015","unstructured":"Bose, P., De Carufel, J., Durocher, S.: Searching on a line: a complete characterization of the optimal solution. Theoret. Comput. Sci. 569, 24\u201342 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1165_CR17","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00453-014-9884-6","volume":"72","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. Algorithmica 72(4), 969\u2013994 (2015)","journal-title":"Algorithmica"},{"key":"1165_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2013.07.022","volume":"532","author":"J Boyar","year":"2014","unstructured":"Boyar, J., Larsen, K.S., Maiti, A.: A comparison of performance measures via online search. Theoret. Comput. Sci. 532, 2\u201313 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1165_CR19","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1145\/1497290.1497300","volume":"5","author":"A Condon","year":"2009","unstructured":"Condon, A., Deshpande, A., Hellerstein, L., Wu, N.: Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Trans. Algorithms 5(2), 241\u20132434 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"1165_CR20","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Search on a Line by Byzantine Robots. In: Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), pp. 27:1\u201327:12 (2016)","DOI":"10.1145\/2933057.2933102"},{"key":"1165_CR21","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theoret. Comput. Sci. 361, 342\u2013355 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1165_CR22","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1086649.1086670","volume":"36","author":"R Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News 36(3), 67\u201381 (2005)","journal-title":"SIGACT News"},{"key":"1165_CR23","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF02764811","volume":"12","author":"S Gal","year":"1972","unstructured":"Gal, S.: A general search game. Israel J. Math. 12, 32\u201345 (1972)","journal-title":"Israel J. Math."},{"key":"1165_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/0127002","volume":"27","author":"S Gal","year":"1974","unstructured":"Gal, S.: Minimax solutions for linear search problems. SIAM J. Appl. Math. 27, 17\u201330 (1974)","journal-title":"SIAM J. Appl. Math."},{"key":"1165_CR25","volume-title":"Search Games","author":"S Gal","year":"1980","unstructured":"Gal, S.: Search Games. Academic Press, London (1980)"},{"key":"1165_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(99)00009-8","volume":"93","author":"C Hipke","year":"1999","unstructured":"Hipke, C., Icking, C., Klein, R., Langetepe, E.: How to find a point in the line within a fixed distance. Discret. Appl. Math. 93, 67\u201373 (1999)","journal-title":"Discret. Appl. Math."},{"key":"1165_CR27","first-page":"234","volume":"49","author":"P Jaillet","year":"1993","unstructured":"Jaillet, P., Stafford, M.: Online searching. Oper. Res. 49, 234\u2013244 (1993)","journal-title":"Oper. Res."},{"key":"1165_CR28","unstructured":"Kao, M-Y., Littman, M.L.: Algorithms for informed cows. In: Proceedings of the AAAI 1997 Workshop on Online Search (1997)"},{"issue":"1","key":"1165_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M-Y Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63\u201380 (1996)","journal-title":"Inf. Comput."},{"key":"1165_CR30","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Koutsoupias, E.: Beyond competitive analysis. In: Beyond the Worst-Case Analysis of Algorithms, pp. 529\u2013546. Cambridge University Press (2020)","DOI":"10.1017\/9781108637435.031"},{"key":"1165_CR31","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Hyperbolic dovetailing. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pp. 616\u2013627 (2009)","DOI":"10.1007\/978-3-642-04128-0_46"},{"key":"1165_CR32","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H., Yannakakis, M.: Searching a fixed graph. In: Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 280\u2013289 (1996)","DOI":"10.1007\/3-540-61440-0_135"},{"key":"1165_CR33","doi-asserted-by":"crossref","unstructured":"Kupavskii, Andrey, Welzl, Emo: Lower bounds for searching robots, some faulty. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 447\u2013453 (2018)","DOI":"10.1145\/3212734.3212745"},{"issue":"1\u20133","key":"1165_CR34","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1016\/j.tcs.2003.08.001","volume":"310","author":"A L\u00f3pez-Ortiz","year":"2004","unstructured":"L\u00f3pez-Ortiz, A., Schuierer, S.: On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. Theoret. Comput. Sci. 310(1\u20133), 527\u2013537 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"1165_CR35","doi-asserted-by":"crossref","unstructured":"McGregor, A., Onak, K., Panigrahy, R.: The oil searching problem. In: Proceedings of the 17th European Symposium on Algorithms (ESA), pp. 504\u2013515 (2009)","DOI":"10.1007\/978-3-642-04128-0_45"},{"issue":"1","key":"1165_CR36","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0925-7721(00)00030-4","volume":"18","author":"S Schuierer","year":"2001","unstructured":"Schuierer, S.: Lower bounds in online geometric searching. Comput. Geom. Theory Appl. 18(1), 37\u201353 (2001)","journal-title":"Comput. Geom. Theory Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01165-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01165-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01165-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T01:21:12Z","timestamp":1703035272000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01165-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,26]]},"references-count":36,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1165"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01165-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,8,26]]},"assertion":[{"value":"20 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors do not have any conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}