{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:44Z","timestamp":1725470744314},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_54","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"600-611","source":"Crossref","is-referenced-by-count":7,"title":["Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing"],"prefix":"10.1007","author":[{"given":"Danny","family":"Segev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"54_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P.N., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing\u00a024(3), 440\u2013456 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR2","unstructured":"Arora, S., Karakostas, G.: A 2\u2009+\u2009\u03b5 approximation algorithm for the k-MST problem. In: 11th SODA, pp. 754\u2013759 (2000)"},{"issue":"3","key":"54_CR3","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"issue":"2","key":"54_CR4","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jagm.1999.1062","volume":"34","author":"Y. Asahiro","year":"2000","unstructured":"Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph. Journal of Algorithms\u00a034(2), 203\u2013221 (2000)","journal-title":"Journal of Algorithms"},{"key":"54_CR5","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D. Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.P.: A note on the prize collecting traveling salesman problem. Mathematical Programming\u00a059, 413\u2013420 (1993)","journal-title":"Mathematical Programming"},{"issue":"1","key":"54_CR6","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. Journal of Computer and System Sciences\u00a058(1), 101\u2013108 (1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"54_CR7","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)","journal-title":"Algorithmica"},{"issue":"2","key":"54_CR8","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U. Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms\u00a041(2), 174\u2013211 (2001)","journal-title":"Journal of Algorithms"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: 37th FOCS, pp. 302\u2013309 (1996)","DOI":"10.1109\/SFCS.1996.548489"},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: A 2-approximation for the k-MST problem in graphs. In: 37th STOC, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"issue":"2","key":"54_CR11","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing\u00a024(2), 296\u2013317 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: 17th SODA, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"issue":"3","key":"54_CR13","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s101070100288","volume":"92","author":"Q. Han","year":"2002","unstructured":"Han, Q., Ye, Y., Zhang, J.: An improved rounding method and semidefinite programming relaxation for graph partition. Mathematical Programming\u00a092(3), 509\u2013535 (2002)","journal-title":"Mathematical Programming"},{"key":"54_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/11671411_25","volume-title":"Approximation and Online Algorithms","author":"A. Levin","year":"2006","unstructured":"Levin, A., Segev, D.: Partial multicuts in trees. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 320\u2013333. Springer, Heidelberg (2006)"},{"issue":"3","key":"54_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"54_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1007\/3-540-61422-2_121","volume-title":"Algorithm Theory - SWAT \u201996","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem (extended abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 66\u201375. Springer, Heidelberg (1996)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:35Z","timestamp":1605642035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11841036_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}