{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:21:30Z","timestamp":1744258890833,"version":"3.40.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T00:00:00Z","timestamp":1736899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T00:00:00Z","timestamp":1736899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study a variant of the offline Dial-a-Ride problem, where each request has a source and destination and the goal is to maximize the number of requests served within a specified time limit. We investigate this problem for the uniform metric space and show that the problem is NP-hard. We then present a 2\/3 approximation algorithm called <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsc {twochain}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mstyle>\n                    <mml:mi>T<\/mml:mi>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mi>C<\/mml:mi>\n                    <mml:mi>H<\/mml:mi>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mi>I<\/mml:mi>\n                    <mml:mi>N<\/mml:mi>\n                  <\/mml:mstyle>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, which simply looks for pairs of requests that are \u201cchained\u201d together and serves those before serving requests that are not connected to any others. We also show that a natural generalization of this algorithm, <jats:italic>k<\/jats:italic>-<jats:sc>chain<\/jats:sc>, has an approximation ratio at most 7\/9. We also analyze the <jats:sc>longest-chain-first<\/jats:sc> algorithm for the problem, characterizing graphs on which it is optimal, and showing that it has an approximation ratio no better than 5\/6. Our experiments on all of these algorithms show that <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsc {twochain}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mstyle>\n                    <mml:mi>T<\/mml:mi>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mi>C<\/mml:mi>\n                    <mml:mi>H<\/mml:mi>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mi>I<\/mml:mi>\n                    <mml:mi>N<\/mml:mi>\n                  <\/mml:mstyle>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is a promising algorithm, performing nearly as well as more computationally intensive variants. We dedicate this article to the memory of Gerhard Woeginger, whose life and work greatly influenced our professional lives, as expanded upon in the Acknowledgments. Woeginger\u2019s prolific research in scheduling, matching, bin-packing, TSP, and online algorithms in general, all served as important parts of the foundation on which our own scholarly pursuits were shaped and formed over the years. Woeginger also studied Dial-a-Ride (DARP) Problems, as DARP is a generalization both of scheduling problems and of TSP, which were two of his most active areas of research.<\/jats:p>","DOI":"10.1007\/s00224-024-10213-8","type":"journal-article","created":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T08:59:47Z","timestamp":1736931587000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximizing Rides Served for Dial-a-Ride on the Uniform Metric"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2493-1251","authenticated-orcid":false,"given":"Barbara M.","family":"Anthony","sequence":"first","affiliation":[]},{"given":"Ricky","family":"Birnbaum","sequence":"additional","affiliation":[]},{"given":"Sara","family":"Boyd","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3580-9275","authenticated-orcid":false,"given":"Christine","family":"Chung","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9445-1475","authenticated-orcid":false,"given":"Ananya","family":"Das","sequence":"additional","affiliation":[]},{"given":"Patrick","family":"Davis","sequence":"additional","affiliation":[]},{"given":"Jigar","family":"Dhimar","sequence":"additional","affiliation":[]},{"given":"Duc","family":"Tran","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9827-0962","authenticated-orcid":false,"given":"David","family":"Yuen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,15]]},"reference":[{"key":"10213_CR1","unstructured":"Anthony, B.M., Birnbaum, R., Boyd, S., Christman, A., Chung, C., Davis, P., Dhimar, J., Yuen, D.S.: Maximizing the number of rides served for Dial-a-Ride. 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2019 75(11), 1\u201315 (2019)"},{"issue":"1","key":"10213_CR2","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.orl.2010.11.004","volume":"39","author":"M Firat","year":"2011","unstructured":"Firat, M., Woeginger, G.J.: Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh. Oper. Res. Lett. 39(1), 32\u201335 (2011). https:\/\/doi.org\/10.1016\/j.orl.2010.11.004","journal-title":"Oper. Res. Lett."},{"key":"10213_CR3","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/j.endm.2015.07.047","volume":"50","author":"P Halffmann","year":"2015","unstructured":"Halffmann, P., Krumke, S.O., Quilliot, A., Wagler, A.K., Wegener, J.-T.: On the online min-wait relocation problem. Electronic Notes in Discrete Mathematics 50, 281\u2013286 (2015)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"1","key":"10213_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","volume":"153","author":"J-F Cordeau","year":"2007","unstructured":"Cordeau, J.-F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29\u201346 (2007). https:\/\/doi.org\/10.1007\/s10479-007-0170-8","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"10213_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10479-017-2525-0","volume":"259","author":"Y Molenbruch","year":"2017","unstructured":"Molenbruch, Y., Braekers, K., Caris, A.: Typology and literature review for dial-a-ride problems. Ann. Oper. Res. 259(1), 295\u2013325 (2017)","journal-title":"Ann. Oper. Res."},{"key":"10213_CR6","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.trb.2018.02.001","volume":"111","author":"SC Ho","year":"2018","unstructured":"Ho, S.C., Szeto, W.Y., Kuo, Y.-H., Leung, J.M.Y., Petering, M., Tou, T.W.H.: A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological 111, 395\u2013421 (2018). https:\/\/doi.org\/10.1016\/j.trb.2018.02.001","journal-title":"Transportation Research Part B: Methodological"},{"key":"10213_CR7","doi-asserted-by":"crossref","unstructured":"Manasse, M., McGeoch, L., Sleator, D.: Competitive algorithms for on-line problems. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 322\u2013333 (1988)","DOI":"10.1145\/62212.62243"},{"key":"10213_CR8","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2012.06.026","volume":"459","author":"M Bienkowski","year":"2012","unstructured":"Bienkowski, M., Kuty\u0142owski, J.: The k-resource problem in uniform metric spaces. Theoret. Comput. Sci. 459, 42\u201354 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.06.026","journal-title":"Theoret. Comput. Sci."},{"key":"10213_CR9","doi-asserted-by":"publisher","unstructured":"Bansal, N., Eli\u00e1\u0161, M., Koumoutsos, G., Nederlof, J.: Competitive algorithms for generalized k-server in uniform metrics. ACM Trans. Algorithms 19(1) (2023). https:\/\/doi.org\/10.1145\/3568677","DOI":"10.1145\/3568677"},{"issue":"4","key":"10213_CR10","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. Journal of the ACM (JACM) 39(4), 745\u2013763 (1992)","journal-title":"Journal of the ACM (JACM)"},{"key":"10213_CR11","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/3-540-45749-6_71","volume-title":"Algorithms \u2013 ESA 2002","author":"H R\u00e4cke","year":"2002","unstructured":"R\u00e4cke, H., Sohler, C., Westermann, M.: Online scheduling for sorting buffers. In: M\u00f6hring, R., Raman, R. (eds.) Algorithms \u2013 ESA 2002, pp. 820\u2013832. Springer, Berlin, Heidelberg (2002)"},{"key":"10213_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-540-24698-5_23","volume-title":"LATIN 2004: Theoretical Informatics","author":"JS Kohrt","year":"2004","unstructured":"Kohrt, J.S., Pruhs, K.: A constant approximation algorithm for sorting buffers. In: Farach-Colton, M. (ed.) LATIN 2004: Theoretical Informatics, pp. 193\u2013202. Springer, Berlin, Heidelberg (2004)"},{"issue":"10","key":"10213_CR13","doi-asserted-by":"publisher","first-page":"1453","DOI":"10.1016\/j.dam.2012.02.005","volume":"160","author":"Y Asahiro","year":"2012","unstructured":"Asahiro, Y., Kawahara, K., Miyano, E.: NP-hardness of the sorting buffer problem on the uniform metric. Discret. Appl. Math. 160(10), 1453\u20131464 (2012). https:\/\/doi.org\/10.1016\/j.dam.2012.02.005","journal-title":"Discret. Appl. Math."},{"key":"10213_CR14","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 954\u2013959 (2006)","DOI":"10.1145\/1109557.1109662"},{"issue":"6","key":"10213_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s10951-007-0037-5","volume":"11","author":"B Csaba","year":"2008","unstructured":"Csaba, B., Pluh\u00e1r, A.: A randomized algorithm for the on-line weighted bipartite matching problem. J. Sched. 11(6), 449\u2013455 (2008)","journal-title":"J. Sched."},{"issue":"2","key":"10213_CR16","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","volume":"68","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Buchbinder, N., Gupta, A., Naor, J.: A randomized o (log2 k)-competitive algorithm for metric bipartite matching. Algorithmica 68(2), 390\u2013403 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"10213_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.orl.2021.12.005","volume":"50","author":"SVS Duppala","year":"2022","unstructured":"Duppala, S.V.S., Sankararaman, K.A., Xu, P.: Online minimum matching with uniform metric and random arrivals. Oper. Res. Lett. 50(1), 45\u201349 (2022). https:\/\/doi.org\/10.1016\/j.orl.2021.12.005","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"10213_CR18","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1287\/moor.1090.0428","volume":"35","author":"B Anthony","year":"2010","unstructured":"Anthony, B., Goyal, V., Gupta, A., Nagarajan, V.: A plant location guide for the unsure: Approximation algorithms for min-max location problems. Math. Oper. Res. 35(1), 79\u2013101 (2010)","journal-title":"Math. Oper. Res."},{"key":"10213_CR19","doi-asserted-by":"publisher","unstructured":"Goodrich, M.T.: Efficient piecewise-linear function approximation using the uniform metric: (preliminary version). In: Proceedings of the Tenth Annual Symposium on Computational Geometry. SCG \u201994, pp. 322\u2013331. Association for Computing Machinery, New York, NY, USA (1994). https:\/\/doi.org\/10.1145\/177424.178040","DOI":"10.1145\/177424.178040"},{"key":"10213_CR20","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: 17th Annual Symposium on Foundations of Computer Science, pp. 216\u2013227 (1976)","DOI":"10.1109\/SFCS.1976.6"},{"issue":"1","key":"10213_CR21","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1006\/jagm.1993.1029","volume":"15","author":"GN Frederickson","year":"1993","unstructured":"Frederickson, G.N., Guan, D.J.: Nonpreemptive ensemble motion planning on a tree. J. Algorithms 15(1), 29\u201360 (1993)","journal-title":"J. Algorithms"},{"key":"10213_CR22","doi-asserted-by":"crossref","unstructured":"Charikar, M., Raghavachari, B.: The finite capacity dial-a-ride problem. In: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pp. 458\u2013467 (1998)","DOI":"10.1109\/SFCS.1998.743496"},{"issue":"2","key":"10213_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721857","volume":"6","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Hajiaghayi, M., Nagarajan, V., Ravi, R.: Dial a ride from k-forest. ACM Transactions on Algorithms (TALG) 6(2), 1\u201321 (2010)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"3","key":"10213_CR24","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s10951-005-6811-3","volume":"8","author":"A Coja-Oghlan","year":"2005","unstructured":"Coja-Oghlan, A., Krumke, S.O., Nierhoff, T.: A hard dial-a-ride problem that is easy on average. J. Sched. 8(3), 197\u2013210 (2005)","journal-title":"J. Sched."},{"key":"10213_CR25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-030-77876-7_3","volume-title":"Mathematical Optimization Theory and Operations Research","author":"BM Anthony","year":"2021","unstructured":"Anthony, B.M., Christman, A.D., Chung, C., Yuen, D.: Serving rides of equal importance for time-limited dial-a-ride. In: Pardalos, P., Khachay, M., Kazakov, A. (eds.) Mathematical Optimization Theory and Operations Research, pp. 35\u201350. Springer, Cham (2021)"},{"key":"10213_CR26","unstructured":"Christman, A., Chung, C., Jaczko, N., Milan, M., Vasilchenko, A., Westvold, S.: Revenue maximization in online dial-a-ride. 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) 59(1), 1\u201315 (2017)"},{"issue":"3","key":"10213_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s43069-021-00076-","volume":"2","author":"AD Christman","year":"2021","unstructured":"Christman, A.D., Chung, C., Jaczko, N., Li, T., Westvold, S., Xu, X., Yuen, D.: Improved Bounds for Revenue Maximization in Time-Limited Online Dial-a-Ride. SN Operations Research Forum 2(3), 1\u201338 (2021). https:\/\/doi.org\/10.1007\/s43069-021-00076-","journal-title":"SN Operations Research Forum"},{"issue":"2","key":"10213_CR28","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/050645464","volume":"37","author":"A Blum","year":"2007","unstructured":"Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput. 37(2), 653\u2013670 (2007)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"10213_CR29","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas, E.: The prize collecting traveling salesman problem. Networks 19(6), 621\u2013636 (1989)","journal-title":"Networks"},{"issue":"1\u20133","key":"10213_CR30","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize collecting traveling salesman problem. Math. Program. 59(1\u20133), 413\u2013420 (1993)","journal-title":"Math. Program."},{"issue":"2","key":"10213_CR31","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10213_CR32","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40(2), 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"key":"10213_CR33","unstructured":"Goemans, M.X.: The prize-collecting TSP revisited. SIAM Conference on Discrete Mathematics (1998)"},{"issue":"3","key":"10213_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s43069-021-00076-x","volume":"2","author":"AD Christman","year":"2021","unstructured":"Christman, A.D., Chung, C., Jaczko, N., Li, T., Westvold, S., Xu, X., Yuen, D.: Improved bounds for revenue maximization in time-limited online dial-a-ride. Operations Research Forum 2(3), 1\u201338 (2021)","journal-title":"Operations Research Forum"},{"key":"10213_CR35","doi-asserted-by":"crossref","unstructured":"Papadimitriou, Christos H and Vazirani, Umesh V: On two geometric problems related to the travelling salesman problem. J. Algorithm 5(2), 231\u2013246 (1984)","DOI":"10.1016\/0196-6774(84)90029-4"},{"key":"10213_CR36","unstructured":"Is the longest trail problem easier than the longest path problem? https:\/\/cstheory.stackexchange.com\/questions\/20682\/"},{"key":"10213_CR37","volume-title":"Algorithms","author":"R Sedgewick","year":"2011","unstructured":"Sedgewick, R., Wayne, K.D.: Algorithms, 4th edn. Addison-Wesley Professional, USA (2011)","edition":"4"},{"key":"10213_CR38","unstructured":"GitHub repository, open source. https:\/\/github.com\/ducttrn\/dial-a-ride"},{"issue":"2","key":"10213_CR39","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/s10878-017-0188-z","volume":"35","author":"A Christman","year":"2018","unstructured":"Christman, A., Forcier, W., Poudel, A.: From theory to practice: maximizing revenues for on-line dial-a-ride. J. Comb. Optim. 35(2), 512\u2013529 (2018)","journal-title":"J. Comb. Optim."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10213-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10213-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10213-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:38:23Z","timestamp":1744216703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10213-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,15]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10213"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10213-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,1,15]]},"assertion":[{"value":"29 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests:"}}],"article-number":"5"}}