{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:08Z","timestamp":1740109268210,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000146","name":"Alberta Innovates - Technology Futures","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000146","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00453-017-0337-x","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T14:29:42Z","timestamp":1497968982000},"page":"2492-2511","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Minimizing Latency of Capacitated k-Tours"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7650-2045","authenticated-orcid":false,"given":"Christopher S.","family":"Martin","sequence":"first","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"issue":"3","key":"337_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"A Ageev","year":"2004","unstructured":"Ageev, A., Sviridenko, M.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"337_CR2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","volume":"6","author":"K Altinkemer","year":"1987","unstructured":"Altinkemer, K., Gavish, B.: Heursitics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4), 149\u2013158 (1987)","journal-title":"Oper. Res. Lett."},{"key":"337_CR3","doi-asserted-by":"crossref","unstructured":"Archer, A., Blasiak, B.: Improved approximation algorithms for the minimum latency problem via prize-collecting strolls. In: 21st ACM SODA, pp. 429\u2013447 (2010)","DOI":"10.1137\/1.9781611973075.36"},{"issue":"5","key":"337_CR4","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1137\/07068151X","volume":"37","author":"A Archer","year":"2008","unstructured":"Archer, A., Levin, A., Williamson, D.P.: A faster, better approximation algorithm for the minimum latency problem. SIAM J. Comput. 37(5), 1472\u20131498 (2008)","journal-title":"SIAM J. Comput."},{"key":"337_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, B., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: 26th ACM STOC, pp. 163\u2013171 (1994)","DOI":"10.1145\/195058.195125"},{"issue":"6","key":"337_CR6","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., Pal, M., Vondrak, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"337_CR7","unstructured":"Carr, B., Vempala, S.: Randomized meta-rounding. In: Proceedings of STOC (2000)"},{"key":"337_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Swamy, C.: Facility location with client laten-cies: linear-programming based techniques for minimum-latency problems. In: 15th IPCO, pp. 92\u2013103 (2011)","DOI":"10.1007\/978-3-642-20807-2_8"},{"key":"337_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Brighten, G., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: 44th IEEE-FOCS, pp. 36\u201345 (2003)","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"337_CR10","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques. Lecture Notes in Computer Science, vol. 3122, pp. 72\u201383. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"337_CR11","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairman problem. In: 14th ACM-SIAM SODA, pp. 655\u2013664 (2003)"},{"key":"337_CR12","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)","DOI":"10.1145\/2591796.2591840"},{"issue":"1\u20132","key":"337_CR13","first-page":"111","volume":"82","author":"M Goemans","year":"1998","unstructured":"Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Math. Program. 82(1\u20132), 111\u2013124 (1998)","journal-title":"Math. Program."},{"issue":"1","key":"337_CR14","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1287\/moor.2014.0656","volume":"40","author":"A Gupta","year":"2015","unstructured":"Gupta, A., Krishnaswamy, R., Nagarajan, V., Ravi, R.: Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res. 40(1), 56\u201379 (2015)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"337_CR15","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"337_CR16","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1016\/j.ejor.2013.08.032","volume":"236","author":"J Lysgaard","year":"2014","unstructured":"Lysgaard, J., Wohlk, S.: A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 236(3), 800\u2013810 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"337_CR17","doi-asserted-by":"crossref","unstructured":"Post, I., Swamy, C.: Linear-programming based approximation algorithms for multi-vehicle minimum latency problems. In: 26th ACM-SIAM SODA, pp. 512\u2013531 (2015)","DOI":"10.1137\/1.9781611973730.35"},{"issue":"1","key":"337_CR18","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10589-014-9713-5","volume":"61","author":"JC Rivera","year":"2015","unstructured":"Rivera, J.C.: Afsar, H.M., Prins, C.: A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem. Comput. Optim. Appl. 61(1), 159\u2013187 (2015)","journal-title":"Comput. Optim. Appl."},{"key":"337_CR19","first-page":"230","volume":"2337","author":"R Sitters","year":"2002","unstructured":"Sitters, R.: The minimum latency problem is NP-hard for weighted trees. IPCO 2337, 230\u2013239 (2002)","journal-title":"IPCO"},{"key":"337_CR20","doi-asserted-by":"crossref","unstructured":"Sitters, R.: Polynomial time approximation schemes for the travelling repairman and other minimum latency problems. In: 25th ACM-SIAM SODA (2014)","DOI":"10.1137\/1.9781611973402.46"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0337-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0337-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0337-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T06:40:49Z","timestamp":1569480049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0337-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,20]]},"references-count":20,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["337"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0337-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,6,20]]}}}