{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T12:34:19Z","timestamp":1751373259538},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,3,26]],"date-time":"2011-03-26T00:00:00Z","timestamp":1301097600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00453-011-9509-2","type":"journal-article","created":{"date-parts":[[2011,3,25]],"date-time":"2011-03-25T15:45:56Z","timestamp":1301067956000},"page":"1017-1030","source":"Crossref","is-referenced-by-count":14,"title":["The Directed Orienteering Problem"],"prefix":"10.1007","volume":"60","author":[{"given":"Viswanath","family":"Nagarajan","sequence":"first","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,26]]},"reference":[{"key":"9509_CR1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1137\/1.9781611973075.32","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"A. Asadpour","year":"2010","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(log\u2009n\/log\u2009log\u2009n)-approximation algorithm for the asymmetric traveling salesman problem. In: ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0379\u2013389 (2010)"},{"key":"9509_CR2","first-page":"166","volume-title":"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: ACM Symposium on Theory of Computing, pp.\u00a0166\u2013174 (2004)"},{"key":"9509_CR3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-642-15369-3_3","volume-title":"Workshop on Approximation Algorithms for Combinatorial Optimization Problems","author":"M. Bateni","year":"2010","unstructured":"Bateni, M., Chuzhoy, J.: Approximation algorithms for the directed k-tour and k-stroll problems. In: Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp.\u00a025\u201338 (2010)"},{"issue":"2","key":"9509_CR4","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/050645464","volume":"37","author":"A. Blum","year":"2007","unstructured":"Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput. 37(2), 653\u2013670 (2007)","journal-title":"SIAM J. Comput."},{"key":"9509_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.\u00a0458\u2013467 (1998)"},{"key":"9509_CR6","first-page":"661","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"C. Chekuri","year":"2008","unstructured":"Chekuri, C., Korula, N., P\u00e1l, M.: Improved algorithms for orienteering and related problems. In: ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0661\u2013670 (2008)"},{"key":"9509_CR7","first-page":"245","volume-title":"IEEE Symposium on Foundations of Computer Science","author":"C. Chekuri","year":"2005","unstructured":"Chekuri, C., Pal, M.: A\u00a0recursive greedy algorithm for walks in directed graphs. In: IEEE Symposium on Foundations of Computer Science, pp.\u00a0245\u2013253 (2005)"},{"key":"9509_CR8","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1287\/opre.40.2.342","volume":"40","author":"M. Desrochers","year":"1992","unstructured":"Desrochers, M., Desrosiers, J., Solomon, M.: A\u00a0new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40, 342\u2013354 (1992)","journal-title":"Oper. Res."},{"key":"9509_CR9","doi-asserted-by":"crossref","unstructured":"Frank, A.: On connectivity properties of Eulerian digraphs. Annals of Discrete Mathematics 41 (1989)","DOI":"10.1016\/S0167-5060(08)70459-X"},{"key":"9509_CR10","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A. Frieze","year":"1982","unstructured":"Frieze, A., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric travelling salesman problem. Networks 12, 23\u201339 (1982)","journal-title":"Networks"},{"key":"9509_CR11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"M.X. Goemans","year":"1993","unstructured":"Goemans, M.X., Bertsimas, D.J.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60, 145\u2013166 (1993)","journal-title":"Math. Program."},{"key":"9509_CR12","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","volume":"34","author":"B.L. Golden","year":"1987","unstructured":"Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Nav. Res. Logist. 34, 307\u2013318 (1987)","journal-title":"Nav. Res. Logist."},{"key":"9509_CR13","doi-asserted-by":"crossref","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. Math. Oper. Res. 10, 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"key":"9509_CR14","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The travelling salesman problem and minimum spanning trees. Oper. Res. 18, 1138\u20131162 (1970)","journal-title":"Oper. Res."},{"issue":"3","key":"9509_CR15","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1002\/jgt.3190120314","volume":"12","author":"B. Jackson","year":"1988","unstructured":"Jackson, B.: Some remarks on arc-connectivity, vertex splitting, and orientation in digraphs. J. Graph Theory 12(3), 429\u2013436 (1988)","journal-title":"J. Graph Theory"},{"key":"9509_CR16","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1057\/jors.1992.88","volume":"43","author":"M. Kantor","year":"1992","unstructured":"Kantor, M., Rosenwein, M.: The orienteering problem with time windows. J. Oper. Res. Soc. 43, 629\u2013635 (1992)","journal-title":"J. Oper. Res. Soc."},{"issue":"3","key":"9509_CR17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"R.M. Karp","year":"1978","unstructured":"Karp, R.M.: A\u00a0characterization of the minimum cycle mean in a digraph. Discrete Math. 23(3), 309\u2013311 (1978)","journal-title":"Discrete Math."},{"key":"9509_CR18","first-page":"266","volume":"36","author":"A. Kohen","year":"1987","unstructured":"Kohen, A., Kan, A.R., Trienekens, H.: Vehicle routing with time windows. Oper. Res. 36, 266\u2013273 (1987)","journal-title":"Oper. Res."},{"key":"9509_CR19","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1287\/opre.40.4.790","volume":"40","author":"C.-L. Li","year":"1992","unstructured":"Li, C.-L., Simchi-Levi, D., Desrochers, M.: On the distance constrained vehicle routing problem. Oper. Res. 40, 790\u2013799 (1992)","journal-title":"Oper. Res."},{"key":"9509_CR20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0195-6698(82)80009-7","volume":"3","author":"W. Mader","year":"1982","unstructured":"Mader, W.: Construction of all n-fold edge-connected digraphs. Eur. J. Comb. 3, 63\u201367 (1982) (in German)","journal-title":"Eur. J. Comb."},{"key":"9509_CR21","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-540-74208-1_19","volume-title":"Workshop on Approximation Algorithms for Combinatorial Optimization Problems","author":"V. Nagarajan","year":"2007","unstructured":"Nagarajan, V., Ravi, R.: Poly-logarithmic approximation algorithms for directed vehicle routing problems. In: Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp.\u00a0257\u2013270 (2007)"},{"key":"9509_CR22","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1999)"},{"key":"9509_CR23","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF02022044","volume":"4","author":"M. Savelsbergh","year":"1985","unstructured":"Savelsbergh, M.: Local search for routing problems with time windows. Ann. Oper. Res. 4, 285\u2013305 (1985)","journal-title":"Ann. Oper. Res."},{"key":"9509_CR24","doi-asserted-by":"crossref","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. Transp. Sci. 29, 17\u201329 (1995)","journal-title":"Transp. Sci."},{"key":"9509_CR25","first-page":"975","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"S. Vempala","year":"1999","unstructured":"Vempala, S., Yannakakis, M.: A\u00a0convex relaxation for the asymmetric TSP. In: ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0975\u2013976 (1999)"},{"key":"9509_CR26","unstructured":"Williamson, D.: Analysis of the Held-Karp heuristic for the traveling salesman problem. Master\u2019s thesis, MIT Computer Science (1990)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9509-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9509-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9509-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,9]],"date-time":"2019-06-09T12:38:02Z","timestamp":1560083882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9509-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,26]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["9509"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9509-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,26]]}}}