{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T13:33:26Z","timestamp":1666877606333},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,11]]},"abstract":"\n We consider the\n k<\/jats:italic>\n -traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 8.497\u03b1-approximation algorithm for this generalization, where \u03b1 denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning\n i<\/jats:italic>\n vertices of a metric. For the latter problem, a (2 + \u03b5)-approximation is known. Our results can be compared with the best-known approximation algorithm using similar techniques for the case\n k<\/jats:italic>\n = 1, which is 3.59\u03b1. Moreover, recent work of Chaudry et al. [2003] shows how to remove the factor of \u03b1, thus improving all of these results by that factor. We are aware of no previous work on the approximability of the present problem. In addition, we give a simple proof of the 3.59\u03b1-approximation result that can be more easily extended to the case of multiple repairmen, and may be of independent interest.\n <\/jats:p>","DOI":"10.1145\/1290672.1290677","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"40","source":"Crossref","is-referenced-by-count":40,"title":["The\n *k<\/i>\n -traveling repairmen problem"],"prefix":"10.1145","volume":"3","author":[{"given":"Jittat","family":"Fakcharoenphol","sequence":"first","affiliation":[{"name":"Kasetsart University"}]},{"given":"Chris","family":"Harrelson","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","volume-title":"Tech. Rep. 1362","author":"Archer A.","year":"2003"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Archer A."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301432"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Arora S."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258602"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195125"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701392056"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 36--45","author":"Chaudry K."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), 439--456","author":"Chekuri C."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Chekuri C. and Kumar A. 2004. Maximum coverage problem with group budget constraints and applications. http:\/\/cm.bell-labs.com\/cm\/cs\/who\/chekuri\/postscript\/coverage.ps. Chekuri C. and Kumar A. 2004. Maximum coverage problem with group budget constraints and applications. http:\/\/cm.bell-labs.com\/cm\/cs\/who\/chekuri\/postscript\/coverage.ps.","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"e_1_2_1_11_1","unstructured":"Christofides N. 1985. The Traveling Salesman Problem. John Wiley New York 431--448. Christofides N. 1985. The Traveling Salesman Problem. John Wiley New York 431--448."},{"key":"e_1_2_1_12_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press\/McGraw-Hill. Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press\/McGraw-Hill."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875522"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Goemans M."},{"key":"e_1_2_1_15_1","unstructured":"Haimovich M. Kan A. R. and Stougie L. 1988. Analysis for heuristics for vehicle routing problems. In Vehicle Routing: Methods and Studies. Elsevier Science Chapter 3. Haimovich M. Kan A. R. and Stougie L. 1988. Analysis for heuristics for vehicle routing problems. In Vehicle Routing: Methods and Studies. Elsevier Science Chapter 3."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.660083"},{"key":"e_1_2_1_18_1","unstructured":"Toth P. and Vigo D. eds. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics Philadelphia PA. Toth P. and Vigo D. eds. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics Philadelphia PA."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1290672.1290677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T02:33:27Z","timestamp":1613788407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1290672.1290677"],"URL":"http:\/\/dx.doi.org\/10.1145\/1290672.1290677","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2007,11]]}}}*