{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:29:39Z","timestamp":1763468979567,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031744976"},{"type":"electronic","value":"9783031744983"}],"license":[{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-74498-3_2","type":"book-chapter","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T11:02:30Z","timestamp":1729335750000},"page":"23-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Invited Paper: A Survey of\u00a0the\u00a0Impact of\u00a0Knowledge on\u00a0the\u00a0Competitive Ratio in\u00a0Linear Search"],"prefix":"10.1007","author":[{"given":"Evangelos","family":"Kranakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,20]]},"reference":[{"key":"2_CR1","unstructured":"Ahlswede, R., Wegener, I.: Search Problems. Wiley-Interscience (1987)"},{"key":"2_CR2","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous, vol. 55. Springer (2003)"},{"key":"2_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105091","volume":"295","author":"S Angelopoulos","year":"2023","unstructured":"Angelopoulos, S.: Online search with a hint. Inf. Comput. 295, 105091 (2023)","journal-title":"Inf. Comput."},{"key":"2_CR4","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."},{"issue":"2","key":"2_CR5","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(2), 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"issue":"3","key":"2_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0925-7721(95)00003-R","volume":"5","author":"R Baeza-Yates","year":"1995","unstructured":"Baeza-Yates, R., Schott, R.: Parallel searching in the plane. Comput. Geom. 5(3), 143\u2013154 (1995)","journal-title":"Comput. Geom."},{"issue":"1","key":"2_CR7","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00453-018-0447-0","volume":"81","author":"E Bampas","year":"2019","unstructured":"Bampas, E., Czyzowicz, J., Gasieniec, L., Ilcinkas, D., Klasing, R., Kociumaka, T., Pajak, D.: Linear search by a pair of distinct-speed robots. Algorithmica 81(1), 317\u2013342 (2019)","journal-title":"Algorithmica"},{"issue":"4","key":"2_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02759737","volume":"2","author":"A Beck","year":"1964","unstructured":"Beck, A.: On the linear search problem. Israel J. Math. 2(4), 221\u2013228 (1964)","journal-title":"Israel J. Math."},{"issue":"4","key":"2_CR9","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."},{"issue":"3","key":"2_CR10","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R.: An optimal search. SIAM Rev. 5(3), 274\u2013274 (1963)","journal-title":"SIAM Rev."},{"issue":"8","key":"2_CR11","doi-asserted-by":"publisher","first-page":"2485","DOI":"10.1007\/s00453-022-01075-y","volume":"85","author":"A Bonato","year":"2023","unstructured":"Bonato, A., Georgiou, K., MacRury, C., Pra\u0142at, P.: Algorithms for $$p$$-faulty search on a half-line. Algorithmica 85(8), 2485\u20132514 (2023)","journal-title":"Algorithmica"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Bonato, A., Nowakowski, R.: The Game of Cops and Robbers on Graphs. American Mathematical Society (2011)","DOI":"10.1090\/stml\/061"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.08.023","volume":"703","author":"P Bose","year":"2017","unstructured":"Bose, P., De Carufel, J.-L.: A general framework for searching on a line. Theoret. Comput. Sci. 703, 1\u201317 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Bose, P., De\u00a0Carufel, J.-L., Durocher, S.: Revisiting the problem of searching on a line. In: Algorithms\u2013ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, Sep. 2-4, 2013. Proceedings 21, pp. 205\u2013216. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_18"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Gasieniec, L.G.T., Martin, R.: Group search on the line. In SOFSEM, pp. 164\u2013176. Springer (2015)","DOI":"10.1007\/978-3-662-46078-8_14"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Coleman, J.R., Ivanov, D., Kranakis, E., Krizanc, D., Morales-Ponce, O.: Linear search for an escaping target with unknown speed. In: Rescigno, A.A., Vaccaro, U. (eds.) IWOCA 2024: 35th International Workshop on Combinatorial Algorithms, 1-3 July 2024, Ischia, Italy. LNCS, vol. 14764, pp. 396\u2013407. Springer (2024)","DOI":"10.1007\/978-3-031-63021-7_30"},{"key":"2_CR17","unstructured":"Coleman, J.R., Kranakis, E., Krizanc, D., Morales-Ponce, O.: Line search for an oblivious moving target. In Hillel, E., Palmieri, R., Rivi\u00e8re, E. (edis.) 26th International Conference on Principles of Distributed Systems, OPODIS 2022, December 13-15, 2022, Brussels, Belgium. LIPIcs, vol. 253, pp. 12:1\u201312:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Gasieniec, L., Gorry, T., Kranakis, E., Martin, R., Pajak, D.: Evacuating robots via unknown exit in a disk. In DISC 2014, Austin, TX, USA, October 12-15, pp. 122\u2013136 (2014)","DOI":"10.1007\/978-3-662-45174-8_9"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2020.11.014","volume":"852","author":"J Czyzowicz","year":"2021","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Lafond, M., Narayanan, L., Opatrny, J., Shende, S.M.: Time-energy tradeoffs for evacuation by two robots in the wireless model. TCS 852, 61\u201372 (2021)","journal-title":"TCS"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.tcs.2019.09.026","volume":"806","author":"J Czyzowicz","year":"2020","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.M.: Priority evacuation from a disk: the case of n = 1, 2, 3. TCS 806, 595\u2013616 (2020)","journal-title":"TCS"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2020.09.023","volume":"846","author":"J Czyzowicz","year":"2020","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.M.: Priority evacuation from a disk: the case of $$n \\ge 4$$. TCS 846, 91\u2013102 (2020)","journal-title":"TCS"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E.: Group search and evacuation. In Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities: Current Research in Moving and Computing. Springer International Publishing, Cham (2019)","DOI":"10.1007\/978-3-030-11072-7_14"},{"issue":"4","key":"2_CR23","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1142\/S0129054121500209","volume":"32","author":"J Czyzowicz","year":"2021","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.M.: Search on a line by byzantine robots. Int. J. Found. Comput. Sci. 32(4), 369\u2013387 (2021)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2_CR24","unstructured":"Czyzowicz, J., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Pankratov, D., Shende, S.M.: Group evacuation on a line by agents with different communication abilities. In: Proceedings of 32nd ISAAC, Dec. 6-8, 2021, Fukuoka, Japan (2021)"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Killick, R., Kranakis, E., Stachowiak, G.: Search and evacuation with a near majority of faulty agents. In: SIAM ACDA21 (Applied and Computational Discrete Algorithms), Pruceedings, pp. 217\u2013227, Seattle, USA, July 19 to 21. SIAM (2021)","DOI":"10.1137\/1.9781611976830.20"},{"issue":"6","key":"2_CR26","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00446-017-0296-0","volume":"32","author":"J Czyzowicz","year":"2019","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J.: Search on a line with faulty robots. Distrib. Comput. 32(6), 493\u2013504 (2019)","journal-title":"Distrib. Comput."},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Linear search with terrain-dependent speeds. In: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, vol. 10236, p. 430. Springer (2017)","DOI":"10.1007\/978-3-319-57586-5_36"},{"issue":"2","key":"2_CR28","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(2), 342\u2013355 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"2_CR29","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(1), 17\u201330 (1974)","journal-title":"SIAM J. Appl. Math."},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Giachoudis, N., Kranakis, E.: Overcoming probabilistic faults in disoriented linear search. In: Rajsbaum, S., Balliu, A., Daymude, J.J., Olivetti, D. (eds.) SIROCCO 2023: June 6th to 9th, 2023, Alcala de Henares, Spain. LNCS, vol. 13892, pp. 520\u2013535 (2023). Full version in TCS (2024)","DOI":"10.1007\/978-3-031-32733-9_23"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2022.10.013","volume":"939","author":"K Georgiou","year":"2023","unstructured":"Georgiou, K., Lucier, J.: Weighted group search on a line & implications to the priority evacuation problem. Theoret. Comput. Sci. 939, 1\u201317 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Jawhar, K., Kranakis, E.: Bike assisted evacuation on a line. In: SOFSEM 2021, Bolzano-Bozen, Italy, January 25-29, 2021, Proceedings. LNCS, vol. 12607, pp. 104\u2013118. Springer (2021)","DOI":"10.1007\/978-3-030-67731-2_8"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Jawhar, K., Kranakis, E.: Bike assisted evacuation on a line of robots with communication faults. In: ALGOWIN 2024, Royal Holloway, University of London in Egham, United Kingdom, Sep. 5-6, 2024, Proceedings. LNCS. Springer (2024)","DOI":"10.1007\/978-3-031-74580-5_7"},{"issue":"1","key":"2_CR34","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\u201379 (1996)","journal-title":"Inf. Comput."},{"key":"2_CR35","unstructured":"Killick, R.: Search and Rendezvous by Mobile Robots in Continuous Domains. PhD thesis, School of Computer Science, Carleton University (2021)"},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"Kupavskii, A., Welzl, E.: Lower bounds for searching robots, some faulty. In: PODC 2018, pp. 447\u2013453. ACM, Egham, UK (2018)","DOI":"10.1145\/3212734.3212745"},{"issue":"2","key":"2_CR37","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S0304-3975(00)00144-4","volume":"261","author":"A L\u00f3pez-Ortiz","year":"2001","unstructured":"L\u00f3pez-Ortiz, A., Schuierer, S.: The ultimate strategy to search on m rays? Theoret. Comput. Sci. 261(2), 267\u2013295 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR38","doi-asserted-by":"crossref","unstructured":"McCabe, B.J.: Searching for a one-dimensional random walker. J. Appl. Prob. 86\u201393 (1974)","DOI":"10.1017\/S0021900200036421"},{"key":"2_CR39","volume-title":"Theory of Optimal Search","author":"L Stone","year":"1975","unstructured":"Stone, L.: Theory of Optimal Search. Academic Press, New York (1975)"},{"key":"2_CR40","doi-asserted-by":"crossref","unstructured":"Sun, X., Sun, Y., Zhang, J.: Better upper bounds for searching on a line with byzantine robots. In: Complexity and Approximation, pp. 151\u2013171 (2020)","DOI":"10.1007\/978-3-030-41672-0_9"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-74498-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T22:03:04Z","timestamp":1735596184000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-74498-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,20]]},"ISBN":["9783031744976","9783031744983"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-74498-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,10,20]]},"assertion":[{"value":"20 October 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nagoya","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sss2024.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}