{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:40:42Z","timestamp":1787510442839,"version":"build-2736575974"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2012,4,5]],"date-time":"2012-04-05T00:00:00Z","timestamp":1333584000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1007\/s10107-012-0537-8","type":"journal-article","created":{"date-parts":[[2012,4,4]],"date-time":"2012-04-04T03:25:14Z","timestamp":1333509914000},"page":"479-506","source":"Crossref","is-referenced-by-count":19,"title":["On generalizations of network design problems with degree bounds"],"prefix":"10.1007","volume":"141","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":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Britta","family":"Peis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"537_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1287\/moor.1090.0428","volume":"35","author":"B. Anthony","year":"2010","unstructured":"Anthony B., Goyal V., Gupta A., Nagarajan V.: A plant location guide for the unsure: approximation algorithms for min\u2013max location problems. Math. Oper. Res. 35, 79\u2013101 (2010)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"537_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora S., Babai L., Stern J., Sweedyk Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"537_CR3","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"537_CR4","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.1137\/080734340","volume":"39","author":"N. Bansal","year":"2009","unstructured":"Bansal N., Khandekar R., Nagarajan V.: Additive guarantees for degree-bounded directed network design. SIAM J. Comput. 39(4), 1413\u20131431 (2009)","journal-title":"SIAM J. Comput."},{"key":"537_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., K\u00f6nemann, J., Nagarajan, V., Peis, B.: On generalizations of network design problems with degree bounds. In: Proceedings of Integer Programming Combinatorial Optimization (IPCO), pp. 110\u2013123 (2010)","DOI":"10.1007\/978-3-642-13036-6_9"},{"key":"537_CR6","doi-asserted-by":"crossref","unstructured":"Bilo,V., Goyal, V., Ravi, R., Singh, M.: On the crossing spanning tree problem, In: Proceedings of Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 51\u201360 (2004)","DOI":"10.1007\/978-3-540-27821-4_5"},{"issue":"1","key":"537_CR7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M. Charikar","year":"2002","unstructured":"Charikar M., Guha S., Tardos E., Shmoys D.B.: A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci. 65(1), 129\u2013149 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"537_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, D.B., Newman, A., Nikolov, A.: Tight hardness results for minimizing discrepancy. In: Proceedings of Sympoisum on Discrete Algorithms (SODA), pp. 1607\u20131614 (2011)","DOI":"10.1137\/1.9781611973082.124"},{"issue":"1","key":"537_CR9","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/s00453-007-9115-5","volume":"55","author":"K. Chaudhuri","year":"2009","unstructured":"Chaudhuri K., Rao S., Riesenfeld S., Talwar K.: What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs. Algorithmica. 55(1), 157\u2013189 (2009)","journal-title":"Algorithmica."},{"issue":"44","key":"537_CR10","doi-asserted-by":"crossref","first-page":"4489","DOI":"10.1016\/j.tcs.2009.07.029","volume":"410","author":"K. Chaudhuri","year":"2009","unstructured":"Chaudhuri K., Rao S., Riesenfeld S., Talwar K.: A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids. Theor. Comput. Sci. 410(44), 4489\u20134503 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"537_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B. Chazelle","year":"2000","unstructured":"Chazelle B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2000)"},{"key":"537_CR12","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via Exchange Properties of Combinatorial Structures. In: Proceedings of Foundations of Computer Science (FOCS), 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"key":"537_CR13","unstructured":"Faigle, U., Peis, B.: Two-phase greedy algorithms for some classes of combinatorial linear programs. In: Proceedings of Symposium on Discrete Algorithms (SODA), pp. 161\u2013166 (2008)"},{"key":"537_CR14","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s101070050040","volume":"84","author":"A. Frank","year":"1999","unstructured":"Frank A.: Increasing the rooted connectivity of a digraph by one. Math. Program. 84, 565\u2013576 (1999)","journal-title":"Math. Program."},{"key":"537_CR15","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum bounded-degree spanning trees. In: Proceedings of Foundations of Computer Scienc (FOCS), pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"537_CR16","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Ravi, R., Singh, M.: Iterative rounding for multiobjective optimization problems. In: Proceedings of European Symposium on Algorithms (ESA), pp. 95\u2013106 (2009)","DOI":"10.1007\/978-3-642-04128-0_9"},{"key":"537_CR17","unstructured":"Hoffman, A., Schwartz, D.E.: On lattice polyhedra. In: Hajnal A., Sos V.T. (eds.) Proceedings of Fifth Hungarian Combinatorial Coll., North-Holland, Amsterdam, pp. 593\u2013598 (1978)"},{"key":"537_CR18","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica. 21, 39\u201360 (2001)","journal-title":"Combinatorica."},{"key":"537_CR19","doi-asserted-by":"crossref","unstructured":"Kir\u00e1ly, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 259\u2013272 (2008)","DOI":"10.1007\/978-3-540-68891-4_18"},{"key":"537_CR20","doi-asserted-by":"crossref","first-page":"1783","DOI":"10.1137\/S009753970036917X","volume":"31","author":"J. K\u00f6nemann","year":"2002","unstructured":"K\u00f6nemann J., Ravi R.: A matter of degree: improved approximation algorithms for degree bounded minimum spanning trees. SIAM J. Comput. 31, 1783\u20131793 (2002)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"537_CR21","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539702418048","volume":"34","author":"J. K\u00f6nemann","year":"2005","unstructured":"K\u00f6nemann J., Ravi R.: Primal-dual meets local search: approximating MSTs with nonuniform degree bounds. SIAM J. Comput. 34(3), 763\u2013773 (2005)","journal-title":"SIAM J. Comput."},{"key":"537_CR22","volume-title":"Combinatorial Optimization, 4th edn","author":"B. Korte","year":"2008","unstructured":"Korte B., Vygen J.: Combinatorial Optimization, 4th edn. Springer, New York (2008)"},{"issue":"3","key":"537_CR23","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1137\/070700620","volume":"39","author":"L.C. Lau","year":"2009","unstructured":"Lau L.C., Naor J., Salavatipour M. R., Singh M.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062\u20131087 (2009)","journal-title":"SIAM J. Comput."},{"key":"537_CR24","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 759\u2013768 (2008)","DOI":"10.1145\/1374376.1374485"},{"key":"537_CR25","doi-asserted-by":"crossref","unstructured":"Matuschke, J., Peis, B.: Lattices and maximum flow algorithms in planar graphs. In: Proceedings of Workshop on Graph Theoretic Concepts in Computer Science (WG), pp. 324\u2013335 (2010)","DOI":"10.1007\/978-3-642-16926-7_30"},{"key":"537_CR26","doi-asserted-by":"crossref","unstructured":"McCormick, S. T., Peis, B.: A Primal-dual algorithm for weighted abstract cut packing. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 324\u2013335 (2011)","DOI":"10.1007\/978-3-642-20807-2_26"},{"key":"537_CR27","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: Approximating directed weighted-degree constrained networks. In: Proceedings of Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 219\u2013232 (2008)","DOI":"10.1007\/978-3-540-85363-3_18"},{"key":"537_CR28","doi-asserted-by":"crossref","unstructured":"Ravi, R. Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 438\u2013447 (1993)","DOI":"10.1145\/167088.167209"},{"key":"537_CR29","doi-asserted-by":"crossref","unstructured":"Ravi, R., Singh, M.: Delegate and conquer: an LP-based approximation algorithm for minimum degree MSTs. In: Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pp. 169\u2013180 (2006)","DOI":"10.1007\/11786986_16"},{"issue":"3","key":"537_CR30","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"537_CR31","volume-title":"Combinatorial Optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver A.: Combinatorial Optimization. Springer, New York (2003)"},{"key":"537_CR32","unstructured":"Singh, M.: Personal Communication (2008)"},{"key":"537_CR33","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0537-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-012-0537-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0537-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,26]],"date-time":"2019-06-26T18:09:08Z","timestamp":1561572548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-012-0537-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,5]]},"references-count":33,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["537"],"URL":"https:\/\/doi.org\/10.1007\/s10107-012-0537-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,5]]}}}