{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:37:49Z","timestamp":1767339469166,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0430751CCF-0728841","CCF-0448095"],"award-info":[{"award-number":["CCF-0430751CCF-0728841","CCF-0448095"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            The\n            <jats:italic>k-forest problem<\/jats:italic>\n            is a common generalization of both the\n            <jats:italic>k-MST<\/jats:italic>\n            and the\n            <jats:italic>dense-k-subgraph<\/jats:italic>\n            problems. Formally, given a metric space on\n            <jats:italic>n<\/jats:italic>\n            vertices\n            <jats:italic>V<\/jats:italic>\n            , with\n            <jats:italic>m<\/jats:italic>\n            demand pairs \u2286\n            <jats:italic>V<\/jats:italic>\n            \u00d7\n            <jats:italic>V<\/jats:italic>\n            and a \u201ctarget\u201d\n            <jats:italic>k<\/jats:italic>\n            \u2264\n            <jats:italic>m<\/jats:italic>\n            , the goal is to find a minimum cost subgraph that connects\n            <jats:italic>at least<\/jats:italic>\n            <jats:italic>k<\/jats:italic>\n            pairs. In this paper, we give an\n            <jats:italic>O<\/jats:italic>\n            (min{\u221a\n            <jats:italic>n<\/jats:italic>\n            \u22c5log\n            <jats:italic>k<\/jats:italic>\n            ,\u221a\n            <jats:italic>k<\/jats:italic>\n            })-approximation algorithm for\n            <jats:italic>k<\/jats:italic>\n            -forest, improving on the previous best ratio of\n            <jats:italic>O<\/jats:italic>\n            (min {\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ,\u221a\n            <jats:italic>m<\/jats:italic>\n            }log\n            <jats:italic>n<\/jats:italic>\n            ) by Segev and Segev.\n          <\/jats:p>\n          <jats:p>\n            We then apply our algsorithm for\n            <jats:italic>k<\/jats:italic>\n            -forest to obtain approximation algorithms for several\n            <jats:italic>Dial-a-Ride<\/jats:italic>\n            problems. The basic Dial-a-Ride problem is the following: given an\n            <jats:italic>n<\/jats:italic>\n            point metric space with\n            <jats:italic>m<\/jats:italic>\n            objects each with its own source and destination, and a vehicle capable of carrying\n            <jats:italic>at most<\/jats:italic>\n            <jats:italic>k<\/jats:italic>\n            objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We want that the tour be\n            <jats:italic>non-preemptive<\/jats:italic>\n            : that is, each object, once picked up at its source, is dropped only at its destination. We prove that an \u03b1-approximation algorithm for the\n            <jats:italic>k<\/jats:italic>\n            -forest problem implies an\n            <jats:italic>O<\/jats:italic>\n            (\u03b1\u22c5log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-approximation algorithm for Dial-a-Ride. Using our results for\n            <jats:italic>k<\/jats:italic>\n            -forest, we get an\n            <jats:italic>O<\/jats:italic>\n            (min{\u221a\n            <jats:italic>n<\/jats:italic>\n            ,\u221a\n            <jats:italic>k<\/jats:italic>\n            }\u22c5log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-approximation by Charikar and Raghavachari; our results give a different proof of a similar approximation guarantee\u2014in fact, when the vehicle capacity\n            <jats:italic>k<\/jats:italic>\n            is large, we give a slight improvement on their results. The reduction from Dial-a-Ride to the\n            <jats:italic>k<\/jats:italic>\n            -forest problem is fairly robust, and allows us to obtain approximation algorithms (with the same guarantee) for some interesting generalizations of Dial-a-Ride.\n          <\/jats:p>","DOI":"10.1145\/1721837.1721857","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Dial a Ride from\n            <i>k<\/i>\n            -forest"],"prefix":"10.1145","volume":"6","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"AT&amp;T Research Labs, Florham Park, NJ"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103437"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007385"},{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Blum A.","key":"e_1_2_1_3_1","unstructured":"Blum , A. , Chawla , S. , Karger , D. R. , Lane , T. , Meyerson , A. , and Minkoff , M . 2003. Approximation algorithms for orienteering and discounted-reward TSP . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 46--55. Blum, A., Chawla, S., Karger, D. R., Lane, T., Meyerson, A., and Minkoff, M. 2003. Approximation algorithms for orienteering and discounted-reward TSP. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 46--55."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Charikar M.","key":"e_1_2_1_5_1","unstructured":"Charikar , M. , and Raghavachari , B . 1998. The finite capacity dial-a-ride problem . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 458--467. Charikar, M., and Raghavachari, B. 1998. The finite capacity dial-a-ride problem. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 458--467."},{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Chaudhuri K.","key":"e_1_2_1_6_1","unstructured":"Chaudhuri , K. , Godfrey , B. , Rao , S. , and Talwar , K . 2003. Paths, trees, and minimum latency tours . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 36--45. Chaudhuri, K., Godfrey, B., Rao, S., and Talwar, K. 2003. Paths, trees, and minimum latency tours. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 36--45."},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Fakcharoenphol J.","key":"e_1_2_1_8_1","unstructured":"Fakcharoenphol , J. , Harrelson , C. , and Rao , S . 2003. The k-traveling repairman problem . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 655--664. Fakcharoenphol, J., Harrelson, C., and Rao, S. 2003. The k-traveling repairman problem. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 655--664."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060650"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_20"},{"volume-title":"Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Goemans M. X.","key":"e_1_2_1_15_1","unstructured":"Goemans , M. X. , and Williamson , D. P . 1992. A general approximation technique for constrained forest problems . In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 307--316. Goemans, M. X., and Williamson, D. P. 1992. A general approximation technique for constrained forest problems. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 307--316."},{"key":"e_1_2_1_16_1","volume-title":"SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Gupta A.","year":"2001","unstructured":"Gupta , A. 2001 . Steiner points in tree metrics don't (really) help . In SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 220--227. Gupta, A. 2001. Steiner points in tree metrics don't (really) help. In SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 220--227."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.527"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109626"},{"key":"e_1_2_1_19_1","unstructured":"Krumke S. Rambau J. and Weider S. 2000. An approximation algorithm for the nonpreemptive capacitated dial-a-ride problem. Preprint 00-53 Konrad-Zuse-Zentrum fr Informationstechnik Berlin.  Krumke S. Rambau J. and Weider S. 2000. An approximation algorithm for the nonpreemptive capacitated dial-a-ride problem. Preprint 00-53 Konrad-Zuse-Zentrum fr Informationstechnik Berlin."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.29.1.17"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_54"},{"volume-title":"Discrete Probability and Algorithms. IMA","author":"Steele J. M.","key":"e_1_2_1_23_1","unstructured":"Steele , J. M. 1995. Variations on the monotone subsequence theme of Erd\u0151s and Szekeres . In Discrete Probability and Algorithms. IMA Vol. Math. Appl., vol. 72 . Springer-Verlag , New York , 111--131. Steele, J. M. 1995. Variations on the monotone subsequence theme of Erd\u0151s and Szekeres. In Discrete Probability and Algorithms. IMA Vol. Math. Appl., vol. 72. Springer-Verlag, New York, 111--131."},{"key":"e_1_2_1_24_1","unstructured":"van Lint J. H. and Wilson R. M. 1992. A Course in Combinatorics. Cambridge University Press Cambridge MA.  van Lint J. H. and Wilson R. M. 1992. A Course in Combinatorics. Cambridge University Press Cambridge MA."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721857","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721857","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721857"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721857"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721857","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}