{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T16:59:09Z","timestamp":1792947549755,"version":"4.5.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,12,30]],"date-time":"2005-12-30T00:00:00Z","timestamp":1135900800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2005,12,30]],"date-time":"2005-12-30T00:00:00Z","timestamp":1135900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2006,7]]},"DOI":"10.1007\/s10107-005-0693-1","type":"journal-article","created":{"date-parts":[[2005,12,30]],"date-time":"2005-12-30T06:06:17Z","timestamp":1135922777000},"page":"491-504","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["A 2 + \u025b approximation algorithm for the k-MST problem"],"prefix":"10.1007","volume":"107","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Karakostas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,12,30]]},"reference":[{"key":"693_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"Agrawal","year":"3","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput, 24 (3), 440\u2013456 (1995)","journal-title":"SIAM J. Comput,"},{"key":"693_CR2","unstructured":"Archer, A., Williamson, D.P.: Faster approximation algorithms for the minimum latency problem. In: Proceedings of 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2003, pp. 88\u201396"},{"key":"693_CR3","first-page":"1","volume":"45","author":"Arora","year":"5","unstructured":"Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45 (5), 1\u201330, (1998) Preliminary versions in Proceedings of 37th IEEE Symp. on Foundations of Computer Science (FOCS), pp. 2\u201312, 1996, and in Proceedings of 38th IEEE Symp. on Foundations of Computer Science (FOCS), 1997, pp. 554\u2013563","journal-title":"J. ACM"},{"issue":"3","key":"693_CR4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0020-0190(98)00010-6","volume":"65","author":"S. Arya","year":"1998","unstructured":"Arya, S., Ramesh, H.: 2.5-factor approximation algorithm for the k-MST problem. Information Processing Letters 65 (3), 117\u2013118 (1998)","journal-title":"Information Processing Letters"},{"key":"693_CR5","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"Awerbuch","year":"1","unstructured":"Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum weight k-trees and prize-collecting salesmen. SIAM J. Comput. 28 (1), 254\u2013262 (1998)","journal-title":"SIAM J. Comput."},{"key":"693_CR6","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of 26th ACM Symp. on Theory Of Computing (STOC), 1994, pp. 163\u2013171","DOI":"10.1145\/195058.195125"},{"key":"693_CR7","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jcss.1997.1542","volume":"58","author":"Blum","year":"1","unstructured":"Blum, A., Ravi, R., Vempala, S.: A constant factor approximation for the k-MST problem. J. Comput. Syst. Sci. 58 (1), 101\u2013108 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"693_CR8","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees and minimum latency tours. In: Proceedings of 44th IEEE Symp. on Foundations of Computer Science (FOCS), 2003, pp. 36\u201345"},{"key":"693_CR9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230240103","volume":"24","author":"Fischetti","year":"1994","unstructured":"Fischetti, M., Hamacher, H.W., J\u00f6rnsten, K., Maffioli, F.: Weighted k-cardinality trees: complexity and polyhedral structure. Networks 24, 11\u201321 (1994)","journal-title":"Networks"},{"key":"693_CR10","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proceedings of 37th IEEE Symp. on Foundations of Computer Science (FOCS), 1996, pp. 302\u2013309","DOI":"10.1109\/SFCS.1996.548489"},{"key":"693_CR11","unstructured":"Garg, N.: Saving an \u025b: a 2-approximation for the k-MST problem in graphs. In: Proceedings of 37th ACM Symposium on Theory of Computing (STOC), 2005 pp. 396\u2013402"},{"key":"693_CR12","first-page":"111","volume":"82","author":"Goemans","year":"1998","unstructured":"Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Math. Prog. 82, 111\u2013124 (1998)","journal-title":"Math. Prog."},{"key":"693_CR13","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"Goemans","year":"2","unstructured":"Goemans, M., Williamson, D.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24 (2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"693_CR14","unstructured":"Hockbaum, D.: Approximation algorithms for -hard problems. PWS Publishing Company, 1997"},{"key":"693_CR15","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"Mitchell","year":"4","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions spproximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28 (4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"693_CR16","unstructured":"Rajagopalan, S., Vazirani, V.V.: Logarithmic approximation of minimum weight k-trees. Unpublished manuscript, 1995"},{"key":"693_CR17","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"Ravi","year":"2","unstructured":"Ravi, R., Sundaram, R., Marathe, M., Rosenkrantz, D., Ravi, S.: Spanning trees short and small. SIAM J. Disc. Math. 9 (2), 178\u2013200 (1996)","journal-title":"SIAM J. Disc. Math."},{"key":"693_CR18","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer-Verlag, 2001"},{"key":"693_CR19","unstructured":"Zelikovsky, A., Lozevanu, D.: Minimal and bounded trees. In: Tezele Cong. XVIII Acad. Romano-Americane, 1993, pp. 25\u201326"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0693-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-005-0693-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0693-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0693-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T16:07:14Z","timestamp":1736179634000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-005-0693-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,30]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["693"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0693-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,30]]},"assertion":[{"value":"22 June 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}