{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:15:19Z","timestamp":1780636519812,"version":"3.54.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031389054","type":"print"},{"value":"9783031389061","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_4","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"43-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Analysis of\u00a0the\u00a0Lazy Algorithm for\u00a0Open Online Dial-a-Ride"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2654-149X","authenticated-orcid":false,"given":"J\u00falia","family":"Balig\u00e1cs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2085-0454","authenticated-orcid":false,"given":"Yann","family":"Disser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0504-8834","authenticated-orcid":false,"given":"Farehe","family":"Soheil","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-058X","authenticated-orcid":false,"given":"David","family":"Weckbecker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/3-540-46541-3_53","volume-title":"STACS 2000","author":"N Ascheuer","year":"2000","unstructured":"Ascheuer, N., Krumke, S.O., Rambau, J.: Online dial-a-ride problems: minimizing the completion time. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 639\u2013650. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46541-3_53"},{"issue":"2","key":"4_CR2","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-540-27798-9_32","volume":"92","author":"G Ausiello","year":"2004","unstructured":"Ausiello, G., Demange, M., Laura, L., Paschos, V.: Algorithms for the on-line quota traveling salesman problem. Inf. Process. Lett. 92(2), 89\u201394 (2004). https:\/\/doi.org\/10.1007\/978-3-540-27798-9_32","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"4_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1007\/s004530010071","volume":"29","author":"G Ausiello","year":"2001","unstructured":"Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line travelling salesman. Algorithmica 29(4), 560\u2013581 (2001)","journal-title":"Algorithmica"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11750321_1","volume-title":"Theory and Applications of Models of Computation","author":"G Ausiello","year":"2006","unstructured":"Ausiello, G., Allulli, L., Bonifaci, V., Laura, L.: On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol. 3959, pp. 1\u201320. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11750321_1"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-031-18367-6_8","volume-title":"Approximation and Online Algorithms","author":"J Balig\u00e1cs","year":"2022","unstructured":"Balig\u00e1cs, J., Disser, Y., Mosis, N., Weckbecker, D.: An improved algorithm for open online dial-a-ride. In: Chalermsook, P., Laekhanukit, B. (eds.) WAOA 2022. Lecture Notes in Computer Science, vol. 13538, pp. 154\u2013171. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-18367-6_8"},{"key":"4_CR6","unstructured":"Bienkowski, M., Kraska, A., Liu, H.: Traveling repairperson, unrelated machines, and other stories about average completion times. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 28:1\u201328:20 (2021)"},{"key":"4_CR7","unstructured":"Bienkowski, M., Liu, H.: An improved online algorithm for the traveling repairperson problem on a line. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 6:1\u20136:12 (2019)"},{"key":"4_CR8","unstructured":"Birx, A.: Competitive analysis of the online dial-a-ride problem. Ph.D. thesis, TU Darmstadt (2020)"},{"issue":"2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"1409","DOI":"10.1137\/19M1268513","volume":"34","author":"A Birx","year":"2020","unstructured":"Birx, A., Disser, Y.: Tight analysis of the smartstart algorithm for online dial-a-ride on the line. SIAM J. Discrete Math. 34(2), 1409\u20131443 (2020)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"4_CR10","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1007\/s00453-022-01061-4","volume":"85","author":"A Birx","year":"2022","unstructured":"Birx, A., Disser, Y., Schewior, K.: Improved bounds for open online dial-a-ride on the line. Algorithmica 85(5), 1372\u20131414 (2022)","journal-title":"Algorithmica"},{"issue":"1","key":"4_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3422362","volume":"17","author":"A Bjelde","year":"2020","unstructured":"Bjelde, A., et al.: Tight bounds for online TSP on the line. ACM Trans. Algorithms 17(1), 1\u201358 (2020)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1287\/ijoc.13.2.138.10517","volume":"13","author":"M Blom","year":"2001","unstructured":"Blom, M., Krumke, S.O., de Paepe, W.E., Stougie, L.: The online TSP against fair adversaries. INFORMS J. Comput. 13(2), 138\u2013148 (2001)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1007\/s00224-008-9103-4","volume":"45","author":"V Bonifaci","year":"2008","unstructured":"Bonifaci, V., Stougie, L.: Online $$k$$-server routing problems. Theory Comput. Syst. 45(3), 470\u2013485 (2008)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0304-3975(00)00261-9","volume":"268","author":"E Feuerstein","year":"2001","unstructured":"Feuerstein, E., Stougie, L.: On-line single-server dial-a-ride problems. Theor. Comput. Sci. 268(1), 91\u2013105 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"4_CR15","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0166-218X(00)00390-5","volume":"113","author":"D Hauptmeier","year":"2001","unstructured":"Hauptmeier, D., Krumke, S., Rambau, J., Wirth, H.C.: Euler is standing in line dial-a-ride problems with precedence-constraints. Discrete Appl. Math. 113(1), 87\u2013107 (2001)","journal-title":"Discrete Appl. Math."},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-46521-9_11","volume-title":"Algorithms and Complexity","author":"D Hauptmeier","year":"2000","unstructured":"Hauptmeier, D., Krumke, S.O., Rambau, J.: The online dial-a-ride problem under reasonable load. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 125\u2013136. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46521-9_11"},{"issue":"2","key":"4_CR17","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/net.20454","volume":"58","author":"P Jaillet","year":"2011","unstructured":"Jaillet, P., Lu, X.: Online traveling salesman problems with service flexibility. Networks 58(2), 137\u2013146 (2011)","journal-title":"Networks"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1002\/net.21559","volume":"64","author":"P Jaillet","year":"2014","unstructured":"Jaillet, P., Lu, X.: Online traveling salesman problems with rejection options. Networks 64(2), 84\u201395 (2014)","journal-title":"Networks"},{"issue":"3","key":"4_CR19","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1287\/opre.1070.0450","volume":"56","author":"P Jaillet","year":"2008","unstructured":"Jaillet, P., Wagner, M.R.: Generalized online routing: new competitive ratios, resource augmentation, and asymptotic analyses. Oper. Res. 56(3), 745\u2013757 (2008)","journal-title":"Oper. Res."},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-030-14812-6_20","volume-title":"Theory and Applications of Models of Computation","author":"VA Jawgal","year":"2019","unstructured":"Jawgal, V.A., Muralidhara, V.N., Srinivasan, P.S.: Online travelling salesman problem on a circle. In: Gopal, T.V., Watada, J. (eds.) TAMC 2019. LNCS, vol. 11436, pp. 325\u2013336. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-14812-6_20"},{"key":"4_CR21","unstructured":"Krumke, S.O.: Online optimization competitive analysis and beyond. Habilitation thesis, Zuse Institute Berlin (2001)"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45753-4_18","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"SO Krumke","year":"2002","unstructured":"Krumke, S.O., et al.: Non-abusiveness helps: An O(1)-competitive algorithm for minimizing the maximum flow time in the online traveling salesman problem. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 200\u2013214. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45753-4_18"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/11671411_20","volume-title":"Approximation and Online Algorithms","author":"SO Krumke","year":"2006","unstructured":"Krumke, S.O., de Paepe, W.E., Poensgen, D., Lipmann, M., Marchetti-Spaccamela, A., Stougie, L.: On minimizing the maximum flow time in the online dial-a-ride problem. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 258\u2013269. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11671411_20"},{"issue":"1\u20133","key":"4_CR24","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0304-3975(02)00409-7","volume":"295","author":"SO Krumke","year":"2003","unstructured":"Krumke, S.O., de Paepe, W.E., Poensgen, D., Stougie, L.: News from the online traveling repairman. Theor. Comput. Sci. 295(1\u20133), 279\u2013294 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR25","unstructured":"Lipmann, M.: On-line routing. Ph.D. thesis, Technische Universiteit Eindhoven (2003)"},{"issue":"4","key":"4_CR26","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00453-004-1116-z","volume":"40","author":"M Lipmann","year":"2004","unstructured":"Lipmann, M., Lu, X., de Paepe, W.E., Sitters, R.A., Stougie, L.: On-line dial-a-ride problems under a restricted information model. Algorithmica 40(4), 319\u2013329 (2004)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:48Z","timestamp":1690473948000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}