{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:17Z","timestamp":1759639037037},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"},{"type":"electronic","value":"9783540454717"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45471-3_4","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T17:18:22Z","timestamp":1179767902000},"page":"30-39","source":"Crossref","is-referenced-by-count":2,"title":["Linear Time Approximation Schemes for Vehicle Scheduling"],"prefix":"10.1007","author":[{"given":"John E.","family":"Augustine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven S.","family":"Seiden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"issue":"4","key":"4_CR1","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., AND Talamo, M. Algorithms for the on-line travelling salesman. Algorithmica 29, 4 (2001), 560\u2013581.","journal-title":"Algorithmica"},{"issue":"4","key":"4_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1137\/0207031","volume":"7","author":"J. Bruno","year":"1978","unstructured":"Bruno, J., AND Downey, P. Complexity of task sequencing with deadlines, setup times and changeover costs. SIAM Journal on Computing 7, 4 (Nov. 1978), 393\u2013404.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Motwani, R., Raghavan, P., AND Silverstein, C. Constrained TSP and low-power computing. In Proceedings of the 5th International Workshop on Algorithms and Data Structures (Aug. 1997), pp. 104\u2013115.","DOI":"10.1007\/3-540-63307-3_51"},{"key":"4_CR4","unstructured":"Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. Rep. CS-93-13, Carnegie Mellon University, Graduate School of Industrial Administration, 1976."},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Desrosiers, J., Dumas, Y., Solomon, M., AND Soumis, F. Time constrained routing and scheduling. In Network Routing, Volume 8 of Handbooks in Operations Research and Management Science, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, Eds. Elsevier Science, 1995.","DOI":"10.1016\/S0927-0507(05)80106-9"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Engebretsen, L., AND Karpinski, M. Approximation hardness of TSP with bounded metrics. In Proceedings of the 28th Annual International Colloquium on Automata, Languages and Programming (July 2001), pp. 201\u2013212.","DOI":"10.1007\/3-540-48224-5_17"},{"key":"4_CR7","volume-title":"Computers and Intractability: A Guide to the theory of of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., AND Johnson, D. S.Computers and Intractability: A Guide to the theory of of NP-Completeness. Freeman and Company, San Francisco, 1979."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.","DOI":"10.1145\/261342.571216"},{"key":"4_CR9","first-page":"85","volume-title":"Reducibility Among Combinatorial Problems","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M.Reducibility Among Combinatorial Problems. Plenum Press, NY, 1972, pp. 85\u2013103."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Karuno, Y., AND Nagamochi, H. A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times. In Proceedings of the 9th Annual European Symposium on Algorithms (Aug. 2001), pp. 218\u2013229.","DOI":"10.1007\/3-540-44676-1_18"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Karuno, Y., AND Nagamochi, H. A polynomial time approximation scheme for the multi-vehicle scheduling problem on a path with release and handling times. In Proceedings of the 12th International Symposium on Algorithms and Computation (Dec. 2001), pp. 36\u201347.","DOI":"10.1007\/3-540-45678-3_4"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1023\/A:1018928911513","volume":"69","author":"Y. Karuno","year":"1997","unstructured":"Karuno, Y., Nagamochi, H., AND Ibaraki, T. Vehicle scheduling on a tree with release and handling times. Annals of Operations Research 69 (1997), 193\u2013207.","journal-title":"Annals of Operations Research"},{"key":"4_CR13","unstructured":"Karuno, Y., Nagamochi, H., AND Ibaraki, T. A 1.5-approximation for single-vehicle scheduling problem on a line with release and handling times. In Japan-U.S.A. Symposium on Flexible Automation (July 1998), pp. 1363\u20131366."},{"issue":"4","key":"4_CR14","first-page":"256","volume":"35","author":"H. Nagamochi","year":"1997","unstructured":"Nagamochi, H., Mochizuki, K., AND Ibaraki, T. Complexity of the single vehicle scheduling problem on graphs. INFOR: Information Systems and Operational Research 35, 4 (1997), 256\u2013276.","journal-title":"INFOR: Information Systems and Operational Research"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C. H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C. H. The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science 4, 3 (June 1977), 237\u2013244.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"4_CR16","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1287\/mnsc.36.2.212","volume":"36","author":"H. Psaraftis","year":"1990","unstructured":"Psaraftis, H., Solomon, M., Magnanti, T., AND Kim, T. Routing and scheduling on a shoreline with release times. Management Science 36, 2 (1990), 212\u2013223.","journal-title":"Management Science"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/net.3230220305","volume":"22","author":"J. Tsitsiklis","year":"1992","unstructured":"Tsitsiklis, J. Special cases of traveling salesman and repairman problems with time windows. Networks 22 (1992), 263\u2013282.","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T06:42:32Z","timestamp":1556433752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438663","9783540454717"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}