{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:10:27Z","timestamp":1763467827667},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_57","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"508-515","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for Time-Dependent Orienteering"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","unstructured":"E. M. Arkin, J. S. B. Mitchell, AND G. Narasimhan, Resource-constrained geometric network optimization, in Proceedings Fourteenth ACM Symposium on Computational Geometry, June 6\u201310, 1998, pp. 307\u2013316.","DOI":"10.1145\/276884.276919"},{"key":"57_CR2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, A. Blum, AND S. Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesman, in Proceedings 27th Annual ACM Sympos. Theory Comput. (STOC 95), pp. 277\u2013283, 1995.","DOI":"10.1145\/225058.225139"},{"key":"57_CR3","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E. Balas","year":"1989","unstructured":"E. Balas, The prize collecting traveling salesperson problem, Networks, 19, pp. 621\u2013636, 1989.","journal-title":"Networks"},{"key":"57_CR4","series-title":"Lect Notes Comput Sci","first-page":"111","volume-title":"Proceedings 17th Annual Symposium on Theoretical Aspects of Computer Science","author":"H.J. Bockenhauer","year":"2000","unstructured":"H.J. Bockenhauer, J. Hromkovic, R. Klasing, S. Seibert, AND W. Unger, An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality, in Proceedings 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Springer Verlag, pp. 111\u2013112, 2000."},{"key":"57_CR5","volume-title":"M.Sc. thesis","author":"B. Broden","year":"2000","unstructured":"B. Broden, Time Dependent Traveling Salesman Problem, M.Sc. thesis, Department of Computer Science, Lund University, Sweden, 2000."},{"key":"57_CR6","unstructured":"J. Cheriyan and R. Ravi, Approximation algorithms for network problems, manuscript, 1998. ( http:\/\/www.gsia.cmu.edu\/andrew\/ravi\/home.html )"},{"key":"57_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/3-540-48447-7_30","volume-title":"Proceedings of the 6th Workshop on Algorithms and Data Structures (WADS)","author":"A. Czumaj","year":"1999","unstructured":"A. Czumaj, I. Finch, L. Gasieniec, A. Gibbons, P. Leng, W. Rytter, AND M. Zito, Efficient Web Searching Using Temporal Factors, in Proceedings of the 6th Workshop on Algorithms and Data Structures (WADS), F. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, eds., Springer Verlag, Lecture Notes in Computer Science, vol. 1663, 1999, pp. 294\u2013305."},{"key":"57_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/3-540-49116-3_35","volume-title":"Proceedings 16th Annual Symposium on Theoretical Aspects of Computer Science","author":"L. Engebretsen","year":"1999","unstructured":"L. Engebretsen, An explicit lower bound for TSP with distances one and two, in Proceedings 16th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Springer Verlag, pp. 373\u2013382, 1999."},{"key":"57_CR9","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","volume":"34","author":"B. G. Golden","year":"1991","unstructured":"B. G. Golden, L. Levy, AND R. Vohra, The orienteering problem, Naval Res. Logistics, 34 (1991), pp. 307\u2013318.","journal-title":"Naval Res. Logistics"},{"key":"57_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-48523-6_36","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP\u201999)","author":"M. Hammar","year":"1999","unstructured":"M. Hammar AND B. Nilsson, Approximation results for kinetic variants of TSP, in Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP\u201999), Springer Verlag, Lecture Notes in Computer Science, vol. 1644, 1999, pp. 392\u2013401."},{"key":"57_CR11","unstructured":"D. S. Johnson, M. Minkoff, AND S. Phillips, The Prize Collecting Steiner Tree Problem: Theory and Practice, Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, (2000), pp. 760\u2013769."},{"key":"57_CR12","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"M. V. Marathe","year":"1998","unstructured":"M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz, H. B. Hunt III, Bicriteria network design problems, J. Algorithms 28 (1998), pp. 142\u2013171.","journal-title":"J. Algorithms"},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou AND S. Vempala, On the approximability of the traveling salesman problem, in Proceedings of the the thirty second ACM STOC, pp. 126\u2013133, 2000.","DOI":"10.1145\/335305.335320"},{"issue":"1","key":"57_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"C.H. Papadimitriou AND M. Yannakakis, The traveling salesman problem with distances one and two, in Mathematics of Operations Research 18(1), pp. 1\u201311, 1993.","journal-title":"Mathematics of Operations Research"},{"key":"57_CR15","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"F. C. R. Spieksma","year":"1999","unstructured":"F. C. R. Spieksma, On the approximability of an interval scheduling problem, Journal of Scheduling 2 (1999), pp. 215\u2013227.","journal-title":"Journal of Scheduling"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T22:12:59Z","timestamp":1556748779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_57","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}