{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:57Z","timestamp":1787340537207,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>In the minimum bounded degree Steiner network problem, we are given an undirected graph with an edge cost for each edge, a connectivity requirement $r_{uv}$ for each pair of vertices $u$ and $v$, and a degree upper bound $b_v$ for each vertex $v$. The task is to find a minimum cost subgraph that satisfies all the connectivity requirements and degree upper bounds. Let $r_{\\max}:=\\max_{u,v} \\{r_{uv}\\}$ and ${\\sc opt}$ be the cost of an optimal solution that satisfies all the degree bounds. We present approximation algorithms that minimize the total cost and the degree violation simultaneously. In the special case when $r_{\\max}=1$, there is a polynomial time algorithm that returns a Steiner forest of cost at most $2{\\sc opt}$ and the degree of each vertex $v$ is at most $b_v+3$. In the general case, there is a polynomial time algorithm that returns a Steiner network of cost at most $2{\\sc opt}$ and the degree of each vertex $v$ is at most $b_v+6r_{\\max}+3$. The algorithms are based on the iterative relaxation method, and the analysis of the algorithms is nearly tight.<\/jats:p>","DOI":"10.1137\/110854461","type":"journal-article","created":{"date-parts":[[2013,12,5]],"date-time":"2013-12-05T13:23:28Z","timestamp":1386249808000},"page":"2217-2242","source":"Crossref","is-referenced-by-count":13,"title":["Additive Approximation for Bounded Degree Survivable Network Design"],"prefix":"10.1137","volume":"42","author":[{"given":"Lap Chi","family":"Lau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,12,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Agrawal, P. Klein, and R. Ravi,\n                      When trees collide: An approximation algorithm for the generalized Steiner problem on networks\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 134-144.","DOI":"10.1145\/103418.103437"},{"key":"atypb2","first-page":"1413","volume":"29","author":"Bansal N.","year":"2009","journal-title":"SIAM J. Comput."},{"key":"atypb3","unstructured":"F. Bauer and A. Varma,\n                      Degree-constrained multicasting in point-to-point networks\n                      , in Proceedings of the 14th Annual Joint Conference of the IEEE Computer and Communication Societies, vol. 1, INFOCOM '95, 1995."},{"key":"atypb4","first-page":"26","author":"Chaudhuri K.","year":"2005","journal-title":"Proceedings of APPROX"},{"key":"atypb5","unstructured":"K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar,\n                      Push relabel and an improved approximation algorithm for the bounded-degree MST problem\n                      , in Proceedings of ICALP, 2006."},{"key":"atypb6","first-page":"41","author":"Feder T.","year":"2006","journal-title":"ECCC Report"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1042"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. X. Goemans,\n                      Minimum bounded-degree spanning trees,\n                      in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 273-282.","DOI":"10.1109\/FOCS.2006.48"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"T. Kir\u00e1ly, L. C. Lau, and M. Singh,\n                      Degree bounded matroids and submodular flows\n                      , Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2008, pp. 259-272.","DOI":"10.1007\/978-3-540-68891-4_18"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/net.20031"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970036917X"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418048"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/070700620"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"L. C. Lau, R. Ravi, and M. Singh,\n                      Iterative Methods in Combinatorial Optimization\n                      , Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511977152"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"A. Louis and N. K. Vishnoi,\n                      Improved algorithm for degree bounded survivable network design problem\n                      , in Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, 2010, pp. 408-419.","DOI":"10.1007\/978-3-642-13731-0_38"},{"key":"atypb17","first-page":"582","author":"Nutov Z.","year":"2012","journal-title":"Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN)"},{"key":"atypb18","first-page":"266","author":"Raghavachari B.","year":"1996","journal-title":"Boston"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0038-2"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. Ravi and M. Singh,\n                      Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs\n                      , in Proceedings of ICALP, 2006.","DOI":"10.1007\/11786986_16"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"M. Singh and L. C. Lau,\n                      Approximating minimum bounded degree spanning trees to within one of optimal\n                      , in Proceedings of the 39th ACM Symposium on Theory of Computing, 2007.","DOI":"10.1145\/1250790.1250887"},{"key":"atypb22","unstructured":"V. Vazirani,\n                      Approximation Algorithms\n                      , Springer, New York, 2001."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110854461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:22Z","timestamp":1787337502000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110854461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110854461"],"URL":"https:\/\/doi.org\/10.1137\/110854461","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}