{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T17:53:10Z","timestamp":1777398790771,"version":"3.51.4"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T00:00:00Z","timestamp":1384214400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s10107-013-0727-z","type":"journal-article","created":{"date-parts":[[2013,11,11]],"date-time":"2013-11-11T05:04:25Z","timestamp":1384146265000},"page":"19-34","source":"Crossref","is-referenced-by-count":3,"title":["A 3\/2-approximation algorithm for some minimum-cost graph problems"],"prefix":"10.1007","volume":"150","author":[{"given":"Basile","family":"Cou\u00ebtoux","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James M.","family":"Davis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,12]]},"reference":[{"key":"727_CR1","doi-asserted-by":"crossref","unstructured":"Cou\u00ebtoux, B.: A 3\/2 approximation for a constrained forest problem. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) Algorithms\u2014ESA 2011, 19th Annual European Symposium, no. 6942 in Lecture Notes in Computer Science, pp. 652\u2013663. Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_55"},{"key":"727_CR2","doi-asserted-by":"crossref","unstructured":"Davis, J.M., Williamson, D.P.: A dual-fitting 3\/2-approximation algorithm for some minimum-cost graph problems. In: Epstein, L., Ferragina, P. (eds.) Algorithms\u2014ESA 2012, 20th Annual European Symposium, no. 7501 in Lecture Notes in Computer Science, pp. 373\u2013382. Springer (2012)","DOI":"10.1007\/978-3-642-33090-2_33"},{"key":"727_CR3","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0167-6377(93)90097-Z","volume":"14","author":"C Imieli\u0144ska","year":"1993","unstructured":"Imieli\u0144ska, C., Kalantari, B., Khachiyan, L.: A greedy heuristic for a minimum-weight forest problem. Oper. Res. Lett. 14, 65\u201371 (1993)","journal-title":"Oper. Res. Lett."},{"key":"727_CR4","doi-asserted-by":"crossref","first-page":"4081","DOI":"10.1016\/j.tcs.2010.07.018","volume":"412","author":"C Bazgan","year":"2011","unstructured":"Bazgan, C., Cou\u00ebtoux, B., Tuza, Z.: Complexity and approximation of the constrained forest problem. Theor. Comput. Sci. 412, 4081\u20134091 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"727_CR5","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J Kruskal","year":"1956","unstructured":"Kruskal, J.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"727_CR6","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/j.orl.2004.11.010","volume":"33","author":"M Laszlo","year":"2005","unstructured":"Laszlo, M., Mukherjee, S.: Another greedy heuristic for the constrained forest problem. Oper. Res. Lett. 33, 629\u2013633 (2005)","journal-title":"Oper. Res. Lett."},{"key":"727_CR7","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.dam.2005.06.006","volume":"154","author":"M Laszlo","year":"2006","unstructured":"Laszlo, M., Mukherjee, S.: A class of heuristics for the constrained forest problem. Discret. Appl. Math. 154, 6\u201314 (2006)","journal-title":"Discret. Appl. Math."},{"key":"727_CR8","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":"727_CR9","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s11590-007-0051-8","volume":"2","author":"M Laszlo","year":"2008","unstructured":"Laszlo, M., Mukherjee, S.: An approximation algorithm for network design problems with downwards-monotone demand functions. Optim. Lett. 2, 171\u2013175 (2008)","journal-title":"Optim. Lett."},{"key":"727_CR10","unstructured":"Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, Chap. 4. PWS Publishing, Boston, MA (1996)"},{"key":"727_CR11","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, Art no. 6 (2013)","DOI":"10.1145\/2432622.2432628"},{"key":"727_CR12","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.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40, 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"key":"727_CR13","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296\u2013317 (1995)","journal-title":"SIAM J. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0727-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/article\/10.1007\/s10107-013-0727-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0727-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T11:05:13Z","timestamp":1564657513000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/10.1007\/s10107-013-0727-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,12]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["727"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/s10107-013-0727-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,12]]}}}