{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T21:13:10Z","timestamp":1771189990078,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540853626","type":"print"},{"value":"9783540853633","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_19","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"233-246","source":"Crossref","is-referenced-by-count":4,"title":["A Constant Factor Approximation for Minimum \u03bb-Edge-Connected k-Subgraph with Metric Costs"],"prefix":"10.1007","author":[{"given":"MohammadAli","family":"Safari","sequence":"first","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"19_CR1","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"B. Awerbuch","year":"1999","unstructured":"Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM J. Computing\u00a028(1), 254\u2013262 (1999)","journal-title":"SIAM J. Computing"},{"issue":"1","key":"19_CR2","first-page":"254","volume":"28","author":"A. Blum","year":"1995","unstructured":"Blum, A., Chawla, S., Karger, D., Lane, T., Meyerson, A., Minkoff, M.: Approximation Algorithms for Orienteering and Discounted-Reward TSP. SIAM J. on Computing\u00a028(1), 254\u2013262 (1999); Earlier version in Proc of STOC 1995","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"19_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jcss.1997.1542","volume":"58","author":"A. Blum","year":"1999","unstructured":"Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the k-MST problem. J. Comput. Syst. Sci.\u00a058(1), 101\u2013108 (1999); Earlier in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996), pp. 442\u2013448","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Vetta, A.: Approximation algorithms for network design with metric costs. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC), pp. 167\u2013175 (2005)","DOI":"10.1145\/1060590.1060616"},{"key":"19_CR5","unstructured":"Chekuri, C., Korula, N.: Min-Cost 2-Connected Subgraphs with k Terminals (manuscript, 2008), http:\/\/arxiv.org\/abs\/0802.2528"},{"key":"19_CR6","unstructured":"Chekuri, C., Korula, N., P\u00e1l, M.: Improved Algorithms for Orienteering and Related Problems. In: Proc of ACM-SIAM SODA (2008)"},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10107-003-0479-2","volume":"100","author":"F. Chudak","year":"2004","unstructured":"Chudak, F., Roughgarden, T., Williamson, D.P.: Approximate MSTs and Steiner trees via the primal-dual method and Lagrangean relaxation. Math. Program.\u00a0100(2), 411\u2013421 (2004)","journal-title":"Math. Program."},{"issue":"3","key":"19_CR8","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica\u00a029(3), 410\u2013421 (2001); Preliminary version in the Proc. 34-th IEEE Symp. on Foundations of Computer Science (FOCS) pp. 692\u2013701 (1993)","journal-title":"Algorithmica"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-Approximation for the minim tree spanning k vertices. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pp. 302\u2013309 (1996)","DOI":"10.1109\/SFCS.1996.548489"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC), pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"19_CR11","doi-asserted-by":"publisher","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\u00a021, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"#cr-split#-19_CR12.1","unstructured":"Lau, L., Naor, S., Salavatipour, M., Singh, M.: Survivable Network Design with Degree or Order Constraints. SIAM J. on Computing (submitted);"},{"key":"#cr-split#-19_CR12.2","unstructured":"Earlier version in Proceedings of the thirty-nineth annual ACM symposium on Theory of computing (STOC) (2007)"},{"key":"19_CR13","unstructured":"Rajagopalan, S., Vazirani, V.: Logarithmic approximation of minimum weight k trees (unpublished manuscript) (1995)"},{"issue":"2","key":"19_CR14","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrants, D.J., Ravi, S.S.: Spanning trees short or small. SIAM Journal on Discrete Mathematics\u00a09(2), 178\u2013200 (1996)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"19_CR15","volume-title":"Combinatorial Optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:12:32Z","timestamp":1738347152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}