{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T06:05:52Z","timestamp":1768457152506,"version":"3.49.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030416713","type":"print"},{"value":"9783030416720","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-41672-0_9","type":"book-chapter","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T02:03:04Z","timestamp":1582164184000},"page":"151-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Better Upper Bounds for Searching on a Line with Byzantine Robots"],"prefix":"10.1007","author":[{"given":"Xiaoming","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jialin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s00453-001-0067-x","volume":"32","author":"S Albers","year":"2002","unstructured":"Albers, S., Kursawe, K., Schuierer, S.: Exploring unknown environments with obstacles. Algorithmica 32(1), 123\u2013143 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"9_CR2","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":"2","key":"9_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF02760028","volume":"3","author":"A Beck","year":"1965","unstructured":"Beck, A.: More on the linear search problem. Israel J. Math. 3(2), 61\u201370 (1965)","journal-title":"Israel J. Math."},{"issue":"4","key":"9_CR4","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":"2","key":"9_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02762672","volume":"14","author":"A Beck","year":"1973","unstructured":"Beck, A., Warren, P.: The return of the linear search problem. Israel J. Math. 14(2), 169\u2013183 (1973)","journal-title":"Israel J. Math."},{"issue":"3","key":"9_CR6","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 (1963)","journal-title":"SIAM Rev."},{"issue":"5","key":"9_CR7","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-662-46078-8_14","volume-title":"SOFSEM 2015: Theory and Practice of Computer Science","author":"M Chrobak","year":"2015","unstructured":"Chrobak, M., G\u0105sieniec, L., Gorry, T., Martin, R.: Group search on the line. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 164\u2013176. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46078-8_14"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-319-72751-6_6","volume-title":"Algorithms for Sensor Systems","author":"H Chuangpishit","year":"2017","unstructured":"Chuangpishit, H., Czyzowicz, J., Kranakis, E., Krizanc, D.: Rendezvous on a line by location-aware robots despite the presence of byzantine faults. In: Fern\u00e1ndez Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 70\u201383. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72751-6_6"},{"issue":"3","key":"9_CR10","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1007\/s00453-016-0233-9","volume":"79","author":"J Czyzowicz","year":"2017","unstructured":"Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Taleb, N.: When patrolmen become corrupted: monitoring a graph using faulty mobile robots. Algorithmica 79(3), 925\u2013940 (2017)","journal-title":"Algorithmica"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., et al.: Search on a line by byzantine robots. In: 27th International Symposium on Algorithms and Computation, vol. 27 (2016)","DOI":"10.1145\/2933057.2933102"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-030-11072-7_14","volume-title":"Distributed Computing by Mobile Entities","author":"J Czyzowicz","year":"2019","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E.: Group search and evacuation. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, pp. 335\u2013370. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-11072-7_14"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J.: Search on a line with faulty robots. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 405\u2013414. ACM (2016)","DOI":"10.1145\/2933057.2933102"},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629656","volume":"11","author":"Y Dieudonn\u00e9","year":"2014","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms (TALG) 11(1), 1 (2014)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"1","key":"9_CR15","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."},{"issue":"2","key":"9_CR16","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1137\/S0097539799348670","volume":"31","author":"F Hoffmann","year":"2001","unstructured":"Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM J. Comput. 31(2), 577\u2013600 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9_CR17","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":"9_CR18","unstructured":"Kleinberg, J.M.: On-line search in a simple polygon. In: SODA, vol. 94, pp. 8\u201315 (1994)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Kupavskii, A., Welzl, E.: Lower bounds for searching robots, some faulty. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 447\u2013453. ACM (2018)","DOI":"10.1145\/3212734.3212745"},{"issue":"3","key":"9_CR20","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. (TOPLAS) 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"key":"9_CR21","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Elsevier, Amsterdam (1996)"},{"issue":"1","key":"9_CR22","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 on-line geometric searching. Comput. Geom. 18(1), 37\u201353 (2001)","journal-title":"Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Complexity and Approximation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41672-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T22:28:05Z","timestamp":1665872885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41672-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030416713","9783030416720"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41672-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}