{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:07Z","timestamp":1759637707793,"version":"3.41.0"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_17","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"199-211","source":"Crossref","is-referenced-by-count":6,"title":["Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing"],"prefix":"10.1007","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"2","key":"17_CR1","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1137\/S0036142993226983","volume":"8","author":"J Bang-Jensen","year":"1995","unstructured":"Bang-Jensen, J., Frank, A., Jackson, B.: Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Discrete Math. 8(2), 155\u2013178 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-TSP and vehicle routing with time windows. In: 36th STOC (2004)","DOI":"10.1145\/1007352.1007385"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: 26th STOC, pp. 163\u2013171 (1994)","DOI":"10.1145\/195058.195125"},{"key":"17_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.: Approximation algorithms for orienteering and discount-reward TSP. SICOMP 37, 653\u2013670 (2007)","journal-title":"SICOMP"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/978-3-642-25591-5_3","volume-title":"Algorithms and Computation","author":"A Bock","year":"2011","unstructured":"Bock, A., Grant, E., K\u00f6nemann, J., Sanit\u00e0, L.: The school bus problem on trees. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 10\u201319. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-25591-5_3"},{"issue":"3","key":"17_CR6","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/moor.2015.0758","volume":"41","author":"D Chakrabarty","year":"2016","unstructured":"Chakrabarty, D., Swamy, C.: Facility location with client latencies: linear-programming based techniques for minimum-latency problems. Math. Oper. Res. 41(3), 865\u2013883 (2016)","journal-title":"Math. Oper. Res."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Godfrey, P.B., Rao, S., Talwar, K.: Paths, trees and minimum latency tours. In: Proceedings of 44th FOCS, pp. 36\u201345 (2003)","DOI":"10.1109\/SFCS.2003.1238179"},{"issue":"3","key":"17_CR8","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/2229163.2229167","volume":"8","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Korula, N., P\u00e1l, M.: Improved algorithms for orienteering and related problems. ACM Trans. Algorithms 8(3), 661\u2013670 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The $$k$$ -traveling repairman problem. ACM Trans. Alg. 3(4), Article 40 (2007)","DOI":"10.1145\/1290672.1290677"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Swamy, C.: Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. In: Proceedings of STOC, pp. 744\u2013753 (2014). Detailed version posted on CS arXiv, November 2013","DOI":"10.1145\/2591796.2591840"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the $$k$$ -MST problem in graphs. In: Proceedings of the 37th STOC, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0167-6377(94)90067-1","volume":"16","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: Approximating minimum-cost graph problems with spanning tree edges. Oper. Res. Lett. 16, 183\u2013189 (1994)","journal-title":"Oper. Res. Lett."},{"key":"17_CR13","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":"BL Golden","year":"1987","unstructured":"Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logist. 34, 307\u2013318 (1987)","journal-title":"Naval Res. Logist."},{"key":"17_CR14","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.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10, 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"17_CR15","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/j.ejor.2009.05.017","volume":"202","author":"J Park","year":"2010","unstructured":"Park, J., Kim, B.: The school bus routing problem: a review. Eur. J. Oper. Res. 202(2), 311\u2013319 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Post, I., Swamy, C.: Linear-programming based techniques for multi-vehicle minimum latency problems. In: Proceedings of 26th SODA, pp. 512\u2013531 (2015)","DOI":"10.1137\/1.9781611973730.35"},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1287\/trsc.1040.0096","volume":"39","author":"M Spada","year":"2005","unstructured":"Spada, M., Bierlaire, M., Liebling, T.: Decision-aiding methodology for the school bus routing and scheduling problem. Transp. Sci. 39, 477\u2013490 (2005)","journal-title":"Transp. Sci."},{"volume-title":"The Vehicle Routing Problem","year":"2002","key":"17_CR18","unstructured":"Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2002)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:21:35Z","timestamp":1750274495000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}