{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T16:45:44Z","timestamp":1732034744836},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,11,16]],"date-time":"2013-11-16T00:00:00Z","timestamp":1384560000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00453-013-9850-8","type":"journal-article","created":{"date-parts":[[2013,11,15]],"date-time":"2013-11-15T17:04:46Z","timestamp":1384535086000},"page":"126-147","source":"Crossref","is-referenced-by-count":8,"title":["Approximating Minimum-Cost Connected T-Joins"],"prefix":"10.1007","volume":"72","author":[{"given":"Joseph","family":"Cheriyan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhihan","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,16]]},"reference":[{"key":"9850_CR1","first-page":"875","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing","author":"H.-C. An","year":"2012","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving Christofides\u2019 algorithm for the s-t path TSP. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 875\u2013886 (2012). CoRR arXiv:1110.4604v2 (2011)"},{"issue":"2","key":"9850_CR2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A. Archer","year":"2011","unstructured":"Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.J.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40(2), 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9850_CR3","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E. Balas","year":"1989","unstructured":"Balas, E.: The prize-collecting traveling salesman problem. Networks 19(6), 621\u2013636 (1989)","journal-title":"Networks"},{"issue":"3","key":"9850_CR4","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0012-365X(87)90097-5","volume":"66","author":"F. Barahona","year":"1987","unstructured":"Barahona, F., Conforti, M.: A construction for binary matroids. Discrete Math. 66(3), 213\u2013218 (1987)","journal-title":"Discrete Math."},{"key":"9850_CR5","first-page":"36","volume-title":"Proceedings of the 44nd Annual IEEE Symposium on Foundations of Computer Science","author":"K. Chaudhuri","year":"2003","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: Proceedings of the 44nd Annual IEEE Symposium on Foundations of Computer Science, pp. 36\u201345 (2003)"},{"key":"9850_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report. Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA (1976)"},{"issue":"2","key":"9850_CR7","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s10107-003-0479-2","volume":"100","author":"F.A. Chudak","year":"2004","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Math. Program. 100(2), 411\u2013421 (2004)","journal-title":"Math. Program."},{"key":"9850_CR8","first-page":"82","volume-title":"Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J., Johnson, E.: Matching: a well-solved class of integer linear programs. In: Guy, R., et al. (eds.) Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, pp. 82\u201392. Gordon & Breach, New York (1970)"},{"key":"9850_CR9","unstructured":"Goemans, M.X.: Combining approximation algorithms for the prize-collecting TSP. CoRR arXiv:0910.0553 (2009)"},{"issue":"2","key":"9850_CR10","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"9850_CR11","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J.A. Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.A.: Analysis of Christofides\u2019 heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10, 291\u2013295 (1991)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9850_CR12","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"9850_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative Methods in Combinatorial Optimization","author":"L.C. Lau","year":"2011","unstructured":"Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization. Cambridge University Press, Cambridge (2011)"},{"key":"9850_CR14","first-page":"560","volume-title":"Proceedings of the 52nd Annual Symposium on Foundations of Computer Science","author":"T. M\u00f6mke","year":"2011","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 560\u2013569 (2011). CoRR arXiv:1104.3090 (2011)"},{"key":"9850_CR15","first-page":"30","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science","author":"M. Mucha","year":"2012","unstructured":"Mucha, M.: 13\/9-Approximation for graphic TSP. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, pp. 30\u201341 (2012). Improved analysis for graphic TSP approximation via matchings. CoRR arXiv:1108.1130 (2011)"},{"key":"9850_CR16","first-page":"550","volume-title":"Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science","author":"S. Oveis Gharan","year":"2011","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 550\u2013559 (2011)"},{"key":"9850_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-642-36694-9_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Seb\u0151","year":"2013","unstructured":"Seb\u0151, A.: Eight-fifth approximation for the path TSP. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 7801, pp. 362\u2013374. Springer, Berlin (2013)"},{"key":"9850_CR18","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for graphic TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. CoRR arXiv:1201.1870v2 (2012)"},{"key":"9850_CR19","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics vol. 24. Springer, Berlin (2003)"},{"key":"9850_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D.P. Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9850-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9850-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9850-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9850-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,16]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9850"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9850-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,16]]}}}