{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:03:48Z","timestamp":1775815428867,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,2]],"date-time":"2015-03-02T00:00:00Z","timestamp":1425254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,3,2]]},"abstract":"\n In the\n Minimum Bounded Degree Spanning Tree<\/jats:italic>\n problem, we are given an undirected graph\n G<\/jats:italic>\n = (\n V, E<\/jats:italic>\n ) with a degree upper bound\n \n B\n v<\/jats:sub>\n <\/jats:italic>\n on each vertex\n v<\/jats:italic>\n \u2208\n V<\/jats:italic>\n , and the task is to find a spanning tree of minimum cost that satisfies all the degree bounds. Let\n OPT<\/jats:sc>\n be the cost of an optimal solution to this problem. In this article we present a polynomial-time algorithm which returns a spanning tree\n T<\/jats:italic>\n of cost at most\n OPT<\/jats:sc>\n and\n \n d\n T<\/jats:sub>\n <\/jats:italic>\n (\n v<\/jats:italic>\n ) \u2264\n \n B\n v<\/jats:sub>\n <\/jats:italic>\n + 1 for all\n v<\/jats:italic>\n , where\n \n d\n T<\/jats:sub>\n <\/jats:italic>\n (\n v<\/jats:italic>\n ) denotes the degree of\n v<\/jats:italic>\n in\n T<\/jats:italic>\n . This generalizes a result of F\u00fcrer and Raghavachari [1994] to weighted graphs, and settles a conjecture of Goemans [2006] affirmatively. The algorithm generalizes when each vertex\n v<\/jats:italic>\n has a degree lower bound\n \n A\n v<\/jats:sub>\n <\/jats:italic>\n and a degree upper bound\n \n B\n v<\/jats:sub>\n <\/jats:italic>\n , and returns a spanning tree with cost at most\n OPT<\/jats:sc>\n and\n \n A\n v<\/jats:sub>\n <\/jats:italic>\n - 1 \u2264\n \n d\n T<\/jats:sub>\n <\/jats:italic>\n (\n v<\/jats:italic>\n ) \u2264\n \n B\n v<\/jats:sub>\n <\/jats:italic>\n + 1 for all\n v<\/jats:italic>\n \u2208\n V<\/jats:italic>\n . This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [2001] for the design of approximation algorithms.\n <\/jats:p>","DOI":"10.1145\/2629366","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T14:08:19Z","timestamp":1425391699000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal"],"prefix":"10.1145","volume":"62","author":[{"given":"Mohit","family":"Singh","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,3,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374486"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.029"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9115-5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0016-z"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90023-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1042"},{"key":"e_1_2_1_10_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.48"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970036917X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418048"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/070700620"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"L. C. Lau R. Ravi and M. Singh. 2011. Iterative Methods in Combinatorial Optimization. Cambridge Tects in Applied Mathematics Cambridge University Press. L. C. Lau R. Ravi and M. Singh. 2011. Iterative Methods in Combinatorial Optimization. Cambridge Tects in Applied Mathematics Cambridge University Press.","DOI":"10.1017\/CBO9780511977152"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374485"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167209"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_16"},{"key":"e_1_2_1_21_1","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver . 2003. Combinatorial Optimization - Polyhedra and Efficiency . Springer . A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Springer."},{"key":"e_1_2_1_23_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"V. V. Vazirani . 2004. Approximation Algorithms . Springer . V. V. Vazirani. 2004. Approximation Algorithms. Springer."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788671"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629366","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629366","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,2]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,2]]}},"alternative-id":["10.1145\/2629366"],"URL":"https:\/\/doi.org\/10.1145\/2629366","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,2]]},"assertion":[{"value":"2013-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}