{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:36Z","timestamp":1787340336527,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity requirements with degree bounds: given a directed graph $G=(V,E)$ with nonnegative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds $\\{a_v,b_v\\}_{v\\in V}$ on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm for this problem using the natural LP relaxation and show that our guarantee is the best possible relative to this LP relaxation. We also obtain similar results for the (more general) class of crossing supermodular requirements. In the absence of edge-costs, our result gives the first additive $O(1)$-approximation guarantee for degree-bounded intersecting\/crossing supermodular connectivity problems. We also consider the minimum crossing spanning tree problem: Given an undirected edge-weighted graph G, edge-subsets $\\{E_i\\}_{i=1}^k$, and nonnegative integers $\\{b_i\\}_{i=1}^k$, find a minimum-cost spanning tree (if it exists) in G that contains at most $b_i$ edges from each set $E_i$. We obtain a $+(r-1)$ additive approximation for this problem, when each edge lies in at most r sets. A special case of this problem is the degree-bounded minimum spanning tree, and our techniques give a substantially shorter proof of the recent $+1$ approximation of Singh and Lau [in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2007, pp. 661\u2013670].<\/jats:p>","DOI":"10.1137\/080734340","type":"journal-article","created":{"date-parts":[[2009,10,16]],"date-time":"2009-10-16T18:24:50Z","timestamp":1255717490000},"page":"1413-1431","source":"Crossref","is-referenced-by-count":34,"title":["Additive Guarantees for Degree-Bounded Directed Network Design"],"prefix":"10.1137","volume":"39","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rohit","family":"Khandekar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,10,16]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10092"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"V. Bil\u00f2, V. Goyal, R. Ravi, and M. Singh,\n                      On the crossing spanning tree problem\n                      , in Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, pp. 51\u201360.","DOI":"10.1007\/978-3-540-27821-4_5"},{"key":"R3","doi-asserted-by":"crossref","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 33rd International Colloquium on Automata, Languages and Programming (ICALP), 2006, pp. 191\u2013201.","DOI":"10.1007\/11786986_18"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70817-3"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050040"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1042"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0061-9"},{"key":"R8","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 (FOCS), 2006, pp. 273\u2013282.","DOI":"10.1109\/FOCS.2006.48"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"T. Kir\u00e1ly, L. C. Lau, and M. Singh,\n                      Degree bounded matroids and submodular flows\n                      , in Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2008, pp. 259\u2013272.","DOI":"10.1007\/978-3-540-68891-4_18"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/net.20031"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970036917X"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"L. C. Lau, J. (S.) Naor, M. R. Salavatipour, and M. Singh,\n                      Survivable network design with degree or order constraints (full version)\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2007, pp. 651\u2013660.","DOI":"10.1145\/1250790.1250886"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681329"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/net.20005"},{"key":"R16","unstructured":"V. Nagarajan, R. Ravi, and M. Singh,\n                      Unified Analysis of LP Extreme Points for Steiner Networks and Traveling Salesman\n                      , manuscript, 2008."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0038-2"},{"key":"R18","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 40th Annual ACM Symposium on Theory of Computing (STOC), 2007, pp. 661\u2013670.","DOI":"10.1145\/1250790.1250887"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080734340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:42Z","timestamp":1787337042000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080734340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,16]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080734340"],"URL":"https:\/\/doi.org\/10.1137\/080734340","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,16]]}}}