{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:26:31Z","timestamp":1725557191762},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130359"},{"type":"electronic","value":"9783642130366"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13036-6_9","type":"book-chapter","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T08:36:09Z","timestamp":1275986169000},"page":"110-123","source":"Crossref","is-referenced-by-count":6,"title":["On Generalizations of Network Design Problems with Degree Bounds"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Rohit","family":"Khandekar","sequence":"additional","affiliation":[]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"Britta","family":"Peis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"9_CR1","doi-asserted-by":"publisher","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.\u00a054(2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded network design. In: STOC, pp. 769\u2013778 (2008)","DOI":"10.1145\/1374376.1374486"},{"key":"9_CR3","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 (full version),Technical Report (2010)","DOI":"10.1007\/978-3-642-13036-6_9"},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-540-27821-4_5","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"V. Bilo","year":"2004","unstructured":"Bilo, V., Goyal, V., Ravi, R., Singh, M.: On the crossing spanning tree problem. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 51\u201360. Springer, Heidelberg (2004)"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/11538462_3","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"K. Chaudhuri","year":"2005","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 26\u201339. Springer, Heidelberg (2005)"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11786986_18","volume-title":"Automata, Languages and Programming","author":"K. Chaudhuri","year":"2006","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: Push relabel and an improved approximation algorithm for the bounded-degree MST problem. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 191\u2013201. Springer, Heidelberg (2006)"},{"key":"9_CR7","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":"9_CR8","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent Randomized Rounding for Matroid Polytopes and Applications (2009), http:\/\/arxiv.org\/abs\/0909.4348"},{"key":"9_CR9","unstructured":"Faigle, U., Peis, B.: Two-phase greedy algorithms for some classes of combinatorial linear programs. In: SODA, pp. 161\u2013166 (2008)"},{"key":"9_CR10","doi-asserted-by":"publisher","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. Programming\u00a084, 565\u2013576 (1999)","journal-title":"Math. Programming"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum Bounded-Degree Spanning Trees. In: FOCS, pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-642-04128-0_9","volume-title":"Algorithms - ESA 2009","author":"F. Grandoni","year":"2009","unstructured":"Grandoni, F., Ravi, R., Singh, M.: Iterative Rounding for Multiobjective Optimization Problems. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 95\u2013106. Springer, Heidelberg (2009)"},{"key":"9_CR13","first-page":"593","volume-title":"Proceedings of Fifth Hungarian Combinatorial Coll","author":"A. Hoffman","year":"1978","unstructured":"Hoffman, A., Schwartz, D.E.: On lattice polyhedra. In: Hajnal, A., Sos, V.T. (eds.) Proceedings of Fifth Hungarian Combinatorial Coll, pp. 593\u2013598. North-Holland, Amsterdam (1978)"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. In: Combinatorica, pp. 39\u201361 (2001)","DOI":"10.1007\/s004930170004"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-540-68891-4_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"T. Kir\u00e1ly","year":"2008","unstructured":"Kir\u00e1ly, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 259\u2013272. Springer, Heidelberg (2008)"},{"issue":"3","key":"9_CR16","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/net.20031","volume":"44","author":"P.N. Klein","year":"2004","unstructured":"Klein, P.N., Krishnan, R., Raghavachari, B., Ravi, R.: Approximation algorithms for finding low degree subgraphs. Networks\u00a044(3), 203\u2013215 (2004)","journal-title":"Networks"},{"key":"9_CR17","doi-asserted-by":"publisher","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. on Computing\u00a031, 1783\u20131793 (2002)","journal-title":"SIAM J. on Computing"},{"issue":"3","key":"9_CR18","doi-asserted-by":"publisher","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. on Computing\u00a034(3), 763\u2013773 (2005)","journal-title":"SIAM J. on Computing"},{"key":"9_CR19","volume-title":"Combinatorial Optimization","author":"B. Korte","year":"2008","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization, 4th edn. Springer, New York (2008)","edition":"4"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints (full version). In: STOC, pp. 651\u2013660 (2007)","DOI":"10.1145\/1250790.1250886"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Singh, M.: Additive Approximation for Bounded Degree Survivable Network Design. In: STOC, pp. 759\u2013768 (2008)","DOI":"10.1145\/1374376.1374485"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-85363-3_18","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Z. Nutov","year":"2008","unstructured":"Nutov, Z.: Approximating Directed Weighted-Degree Constrained Networks. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX 2008 and RANDOM 2008. LNCS, vol.\u00a05171, pp. 219\u2013232. Springer, Heidelberg (2008)"},{"key":"9_CR23","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: STOC, pp. 438\u2013447 (1993)","DOI":"10.1145\/167088.167209"},{"key":"9_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/11786986_16","volume-title":"Automata, Languages and Programming","author":"R. Ravi","year":"2006","unstructured":"Ravi, R., Singh, M.: Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 169\u2013180. Springer, Heidelberg (2006)"},{"key":"9_CR25","volume-title":"Combinatorial Optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Heidelberg (2003)"},{"key":"9_CR26","unstructured":"Singh, M.: Personal Communication (2008)"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13036-6_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:00:27Z","timestamp":1606168827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13036-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130359","9783642130366"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13036-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}