{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:17:00Z","timestamp":1725491820957},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_23","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"241-252","source":"Crossref","is-referenced-by-count":8,"title":["Dial a Ride from k-Forest"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","first-page":"134","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing","author":"A. Agrawal","year":"1991","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized steiner problem on networks. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 134\u2013144. ACM Press, New York (1991)"},{"key":"23_CR2","first-page":"166","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time Windows. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 166\u2013174. ACM Press, New York (2004)"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/SFCS.2003.1238180","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science","author":"A. Blum","year":"2003","unstructured":"Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation Algorithms for Orienteering and Discounted-Reward TSP. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 46\u201355. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"23_CR4","first-page":"192","volume-title":"SODA 1998","author":"M. Charikar","year":"1998","unstructured":"Charikar, M., Chekuri, C., yat Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. In: SODA 1998. Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 192\u2013200. ACM Press, New York (1998)"},{"key":"23_CR5","first-page":"458","volume-title":"IEEE Symposium on Foundations of Computer Science","author":"M. Charikar","year":"1998","unstructured":"Charikar, M., Raghavachari, B.: The Finite Capacity Dial-A-Ride Problem. In: IEEE Symposium on Foundations of Computer Science, pp. 458\u2013467. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 36\u201345 (2003)","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"23_CR7","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. GSIA, CMU-Report 388 (1977)"},{"key":"23_CR8","first-page":"655","volume-title":"Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms","author":"J. Fakcharoenphol","year":"2003","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairman problem. In: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms, pp. 655\u2013664. ACM Press, New York (2003)"},{"issue":"3","key":"23_CR9","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The Dense k -Subgraph Problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"23_CR10","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"G.N. Frederickson","year":"1978","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM Journal on Computing\u00a07(2), 178\u2013193 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1145\/1060590.1060650","volume-title":"Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"N. Garg","year":"2005","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 396\u2013402. ACM Press, New York (2005)"},{"key":"23_CR12","first-page":"307","volume-title":"Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M.X. Goemans","year":"1992","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 307\u2013316. ACM Press, New York (1992)"},{"key":"23_CR13","unstructured":"Gupta, A., Hajiaghayi, M.T., Nagarajan, V., Ravi, R.: Dial a Ride from k-forest (2007), http:\/\/arxiv.org\/abs\/0707.0648"},{"key":"23_CR14","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M. Haimovich","year":"1985","unstructured":"Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research\u00a010, 527\u2013542 (1985)","journal-title":"Mathematics of Operations Research"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1145\/1109557.1109626","volume-title":"SODA 2006","author":"M.T. Hajiaghayi","year":"2006","unstructured":"Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. In: SODA 2006. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 631\u2013640. ACM Press, New York (2006)"},{"key":"23_CR16","unstructured":"Krumke, S., Rambau, J., Weider, S.: An approximation algorithm for the nonpreemptive capacitated dial-a-ride problem. Preprint 00-53, Konrad-Zuse-Zentrum fr Informationstechnik Berlin (2000)"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter Bounds for Graph Steiner Tree Approximation. SIAM Journal on Discrete Mathematics\u00a019, 122\u2013134 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"G\u00f8rtz, I.L.: Hardness of Preemptive Finite Capacity Dial-a-Ride. In: 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (2006)","DOI":"10.1007\/11830924_20"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/trsc.29.1.17","volume":"29","author":"M.W.P. Savelsbergh","year":"1995","unstructured":"Savelsbergh, M.W.P., Sol, M.: The general pickup and delivery problem. Transportation Science\u00a029, 17\u201329 (1995)","journal-title":"Transportation Science"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Segev, D., Segev, G.: Approximate k-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing. In: 14th Annual European Symposium on Algorithms, pp. 600\u2013611 (2006)","DOI":"10.1007\/11841036_54"},{"key":"23_CR21","series-title":"IMA Math. Appl.","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-1-4612-0801-3_9","volume-title":"Discrete probability and algorithms (Minneapolis, MN, 1993)","author":"J.M. Steele","year":"1995","unstructured":"Steele, J.M.: Variations on the monotone subsequence theme of Erd\u0151s and Szekeres. In: Discrete probability and algorithms (Minneapolis, MN, 1993). IMA Math. Appl., vol.\u00a072, pp. 111\u2013131. Springer, New York (1995)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:22:48Z","timestamp":1619518968000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_23","relation":{},"subject":[]}}