{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:34Z","timestamp":1759639054293},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_20","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T08:33:54Z","timestamp":1156494834000},"page":"200-211","source":"Crossref","is-referenced-by-count":7,"title":["Hardness of Preemptive Finite Capacity Dial-a-Ride"],"prefix":"10.1007","author":[{"given":"Inge Li","family":"G\u00f8rtz","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, M.: Hardness of buy-at-bulk network design. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 115\u2013124 (October 2004)","DOI":"10.1109\/FOCS.2004.32"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Bounds on fiber minimization in optical networks with fixed fiber capacity. In: IEEE INFOCOM (2005)","DOI":"10.1109\/INFCOM.2005.1497910"},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1137\/S0097539701392056","volume":"31","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Khuller, S., Raghavachari, B.: Algorithms for capacitated vehicle routing. SICOMP: SIAM Journal on Computing\u00a031(3), 665\u2013682 (2002)","journal-title":"SICOMP: SIAM Journal on Computing"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Raghavachari, B.: The finite capacity dial-a-ride problem. In: IEEE Symposium on Foundations of Computer Science, pp. 458\u2013467 (1998)","DOI":"10.1109\/SFCS.1998.743496"},{"key":"20_CR5","first-page":"431","volume-title":"The Traveling Salesman Problem","author":"N. Christofedes","year":"1985","unstructured":"Christofedes, N.: Vehicle routing. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem, pp. 431\u2013448. John Wiley, Chichester (1985)"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F.: VRP with pickup and delivery. In: Toth, P., Vigo, D. (eds.) The vehicle routing problem, pp. 225\u2013242. Society for Industrial and Applied Mathematics (2001)","DOI":"10.1137\/1.9780898718515.ch9"},{"issue":"3","key":"20_CR7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci.\u00a069(3), 385\u2013497 (2004)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"20_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1006\/jagm.1993.1029","volume":"15","author":"G.N. Frederickson","year":"1993","unstructured":"Frederickson, G.N., Guan, D.J.: Non-preemptive ensemble motion planning on a tree. Journal of Algorithms\u00a015(1), 29\u201360 (1993)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"20_CR9","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":"20_CR10","series-title":"Studies in Management Science and Systems","volume-title":"Vehicle Routing: Methods and Studies","author":"B.L. Golden","year":"1991","unstructured":"Golden, B.L., Assad, A.A.: Vehicle Routing: Methods and Studies. Studies in Management Science and Systems, vol.\u00a016. Elsevier, Amsterdam (1991)"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"G\u00f8rtz, I.L.: Hardness of preemptive finite capacity dial-a-ride. IMADA Preprints 2006 No. 4, University of Southern Denmark (2006)","DOI":"10.1007\/11830924_20"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Guan, D.J.: Routing a vehicle of capacity greater than one. Discrete Applied Mathematics\u00a081(1-3) (1998)","DOI":"10.1016\/S0166-218X(97)00074-7"},{"issue":"4","key":"20_CR13","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M. Haimovich","year":"1985","unstructured":"Haimovich, M., Kan, A.H.G.R.: Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research\u00a010(4), 527\u2013542 (1985)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1287\/trsc.17.3.351","volume":"17","author":"H.N. Psaraftis","year":"1983","unstructured":"Psaraftis, H.N.: An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows. Transportation Science\u00a017(3), 351\u2013357 (1983)","journal-title":"Transportation Science"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:18:30Z","timestamp":1605626310000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11830924_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}