{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T18:11:15Z","timestamp":1791396675168,"version":"4.3.3"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF 0728782"],"award-info":[{"award-number":["CCF 0728782"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,7]]},"abstract":"\n In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph\n G<\/jats:italic>\n =(\n V, E<\/jats:italic>\n ) (directed or undirected), two nodes\n s, t<\/jats:italic>\n \u2208\n V<\/jats:italic>\n and a time limit\n B<\/jats:italic>\n , find an\n s<\/jats:italic>\n -\n t<\/jats:italic>\n walk<\/jats:italic>\n in\n G<\/jats:italic>\n of total length at most\n B<\/jats:italic>\n that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as\n k<\/jats:italic>\n -MST. Orienteering with\n time-windows<\/jats:italic>\n is the more general problem in which each node\n v<\/jats:italic>\n has a specified time-window [\n R<\/jats:italic>\n (\n v<\/jats:italic>\n ),\n D<\/jats:italic>\n (\n v<\/jats:italic>\n )] and a node\n v<\/jats:italic>\n is counted as visited by the walk only if\n v<\/jats:italic>\n is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following:\n <\/jats:p>\n \u2014 A (2+\u03f5) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004].<\/jats:p>\n \n \u2014 An\n O<\/jats:italic>\n (log\n 2<\/jats:sup>\n OPT) approximation for orienteering in directed graphs, where OPT \u2264\n n<\/jats:italic>\n is the number of vertices visited by an optimal solution. Previously, only a quasipolynomial-time algorithm due to Chekuri and P\u00e1l [2005] achieved a polylogarithmic approximation (a ratio of\n O<\/jats:italic>\n (log OPT)).\n <\/jats:p>\n \n \u2014 Given an \u03b1 approximation for orienteering, we show an\n O<\/jats:italic>\n (\u03b1 \u010b max{log OPT, log\n l<\/jats:italic>\n max<\/jats:sub>\n \/\n l<\/jats:italic>\n min<\/jats:sub>\n }) approximation for orienteering with time-windows, where\n l<\/jats:italic>\n max<\/jats:sub>\n and\n l<\/jats:italic>\n min<\/jats:sub>\n are the lengths of the longest and shortest time-windows respectively.\n <\/jats:p>","DOI":"10.1145\/2229163.2229167","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T10:41:09Z","timestamp":1343299269000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":109,"title":["Improved algorithms for orienteering and related problems"],"prefix":"10.1145","volume":"8","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"P\u00e1l","sequence":"additional","affiliation":[{"name":"Google Inc., New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R.","year":"1993","unstructured":"Ahuja , R. , Magnanti , T. , and Orlin , J . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall , Upper Saddle River, NJ. Ahuja, R., Magnanti, T., and Orlin, J. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River, NJ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276919"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0693-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528826X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190602"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007385"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.11.002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645464"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1542"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS'03)","author":"Chaudhuri K.","unstructured":"Chaudhuri , K. , Godfrey , B. , Rao , S. , and Talwar , K . 2003. Paths, trees, and minimum latency tours . In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS'03) . 36--45. Chaudhuri, K., Godfrey, B., Rao, S., and Talwar, K. 2003. Paths, trees, and minimum latency tours. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS'03). 36--45."},{"key":"e_1_2_1_11_1","unstructured":"Chekuri C. and Korula N. 2006. Approximation algorithms for orienteering with time windows. arXiv.org preprint. arXiv:0711.4825v1. Chekuri C. and Korula N. 2006. Approximation algorithms for orienteering with time windows. arXiv.org preprint. arXiv:0711.4825v1."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Chekuri C.","unstructured":"Chekuri , C. , Korula , N. , and P\u00e1l , M . 2008. Improved algorithms for orienteering and related problems . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08) . SIAM, Philadelphia, PA, 661--670. Chekuri, C., Korula, N., and P\u00e1l, M. 2008. Improved algorithms for orienteering and related problems. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08). SIAM, Philadelphia, PA, 661--670."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the APPROX-RANDOM Conference. 72--83","author":"Chekuri C.","unstructured":"Chekuri , C. and Kumar , A . 2004. Maximum coverage problem with group budget constraints and applications . In Proceedings of the APPROX-RANDOM Conference. 72--83 . Chekuri, C. and Kumar, A. 2004. Maximum coverage problem with group budget constraints and applications. In Proceedings of the APPROX-RANDOM Conference. 72--83."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a010"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/060667839"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875522"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060650"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D"},{"key":"e_1_2_1_23_1","volume-title":"Eds","author":"Gutin G.","year":"2002","unstructured":"Gutin , G. and Punnen , A. , Eds . 2002 . The Traveling Salesman Problem and Its Variations. Springer . Gutin, G. and Punnen, A., Eds. 2002. The Traveling Salesman Problem and Its Variations. Springer."},{"key":"e_1_2_1_24_1","volume-title":"Eds","author":"Lawler E.","year":"1985","unstructured":"Lawler , E. , Kan , A. R. , Lenstra , J. , and Shmoys , D. , Eds . 1985 . The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley and Sons . Lawler, E., Kan, A. R., Lenstra, J., and Shmoys, D., Eds. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley and Sons."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_19"},{"key":"e_1_2_1_26_1","volume-title":"Eds","author":"Toth P.","year":"2001","unstructured":"Toth , P. and Vigo , D. , Eds . 2001 . The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM , Philadelphia, PA. Toth, P. and Vigo, D., Eds. 2001. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220305"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229167","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2229163.2229167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:48:52Z","timestamp":1750222132000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2229163.2229167"],"URL":"https:\/\/doi.org\/10.1145\/2229163.2229167","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2009-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}