{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:05Z","timestamp":1740109265906,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,4,25]],"date-time":"2017-04-25T00:00:00Z","timestamp":1493078400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["327620-09","Discovery Accelerator Supplement"],"award-info":[{"award-number":["327620-09","Discovery Accelerator Supplement"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003400","name":"Ontario Ministry of Research and Innovation","doi-asserted-by":"crossref","award":["Early Researcher Award"],"award-info":[{"award-number":["Early Researcher Award"]}],"id":[{"id":"10.13039\/501100003400","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10107-017-1150-7","type":"journal-article","created":{"date-parts":[[2017,4,25]],"date-time":"2017-04-25T08:29:41Z","timestamp":1493108981000},"page":"17-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems"],"prefix":"10.1007","volume":"172","author":[{"given":"Andr\u00e9","family":"Linhares","sequence":"first","affiliation":[]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,25]]},"reference":[{"key":"1150_CR1","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M., Madry, A., Oveis Gharan, S., Saberi, A.: An $$O(\\log n\/\\log \\log n)$$ O ( log n \/ log log n ) -approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 20th SODA, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"issue":"1\u20132","key":"1150_CR2","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s10107-012-0537-8","volume":"141","author":"N Bansal","year":"2013","unstructured":"Bansal, N., Khandekar, R., K\u00f6nemann, J., Nagarajan, V., Peis, B.: On generalizations of network design problems with degree bounds. Math. Program. 141(1\u20132), 479\u2013506 (2013)","journal-title":"Math. Program."},{"issue":"4","key":"1150_CR3","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. SICOMP 39(4), 1413\u20131431 (2009)","journal-title":"SICOMP"},{"key":"1150_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Nagarajan, V.: Approximation-friendly discrepancy rounding. To appear in Proceedings of IPCO 2016. Also appears as arXiv:1512.02254 (2015)","DOI":"10.1007\/978-3-319-44479-6_4"},{"key":"1150_CR5","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, 157\u2013189 (2009)","journal-title":"Algorithmica"},{"key":"1150_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondrak, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: 51st FOCS (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"3","key":"1150_CR7","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms 17(3), 409\u2013423 (1994)","journal-title":"J. Algorithms"},{"key":"1150_CR8","doi-asserted-by":"crossref","unstructured":"Goemans, M.: Minimum bounded degree spanning trees. In: 47th FOCS (2006)","DOI":"10.1109\/FOCS.2006.48"},{"issue":"1\u20132","key":"1150_CR9","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s10107-013-0703-7","volume":"146","author":"F Grandoni","year":"2014","unstructured":"Grandoni, F., Ravi, R., Singh, M., Zenklusen, R.: New approaches to multi-objective optimization. Math. Program. 146(1\u20132), 525\u2013554 (2014)","journal-title":"Math. Program."},{"key":"1150_CR10","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":"1150_CR11","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. SICOMP 31, 1783\u20131793 (2002)","journal-title":"SICOMP"},{"key":"1150_CR12","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Ravi, R.: Primal-dual meets local search: approximating MST\u2019s with nonuniform degree bounds. In: Proceedings of the 35th STOC, pp. 389\u2013395 (2003)","DOI":"10.1145\/780542.780600"},{"key":"1150_CR13","doi-asserted-by":"crossref","unstructured":"Linhares, A., Swamy, C.: Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems. In: Proceedings of the 18th IPCO, pp. 38\u201349 (2016)","DOI":"10.1007\/978-3-319-33461-5_4"},{"key":"1150_CR14","doi-asserted-by":"crossref","unstructured":"Olver, N., Zenklusen, R.: Chain-constrained spanning trees. In: Proceedings of the 16th IPCO, pp. 324\u2013335 (2013)","DOI":"10.1007\/978-3-642-36694-9_28"},{"key":"1150_CR15","doi-asserted-by":"crossref","unstructured":"Ravi, R., Marathe, M., Ravi, S., Rosenkrantz, D., Hunt III, H.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 31(1), 58\u201378 (2001)","DOI":"10.1007\/s00453-001-0038-2"},{"key":"1150_CR16","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the 39th STOC, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"},{"key":"1150_CR17","doi-asserted-by":"crossref","unstructured":"Zenklusen, R.: Matroidal degree-bounded minimum spanning trees. In: Proceedings of the 23rd SODA, pp. 1512\u20131521 (2012)","DOI":"10.1137\/1.9781611973099.120"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1150-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1150-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1150-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T17:39:08Z","timestamp":1569087548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1150-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,25]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["1150"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1150-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2017,4,25]]}}}