{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:25:15Z","timestamp":1760016315931},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540939795"},{"type":"electronic","value":"9783540939801"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-93980-1_14","type":"book-chapter","created":{"date-parts":[[2009,1,12]],"date-time":"2009-01-12T00:12:21Z","timestamp":1231719141000},"page":"174-187","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements"],"prefix":"10.1007","author":[{"given":"Chandrashekhar","family":"Nagarajan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yogeshwer","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"14_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 J. Comput.\u00a024(3), 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E. Balas","year":"1989","unstructured":"Balas, E.: The prize collecting traveling salesman problem. Networks\u00a019, 621\u2013636 (1989)","journal-title":"Networks"},{"key":"14_CR3","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. Math. Programming\u00a059, 413\u2013420 (1993)","journal-title":"Math. Programming"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/978-3-540-75520-3_60","volume-title":"Algorithms \u2013 ESA 2007","author":"M. Chimani","year":"2007","unstructured":"Chimani, M., Kandyba, M., Mutzel, P.: A new ILP formulation for 2-root-connected prize-collecting steiner networks. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 681\u2013692. Springer, Heidelberg (2007)"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jcss.2001.1754","volume":"63","author":"J. Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Papadimitriou, C.H., Shenker, S.: Sharing the cost of multicast transmissions. Journal of Computer and System Sciences\u00a063, 21\u201341 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"M.X. Goemans","year":"1993","unstructured":"Goemans, M.X., Bertsimas, D.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program.\u00a060, 145\u2013166 (1993)","journal-title":"Math. Program."},{"key":"14_CR7","unstructured":"Goemans, M.: Personal communication (1998)"},{"issue":"2","key":"14_CR8","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 J. Comput.\u00a024(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: SODA, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"14_CR10","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: SODA, pp. 933\u2013942 (2005)"},{"issue":"1","key":"14_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(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"14_CR12","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: SODA, pp. 760\u2013769 (2000)"},{"key":"14_CR13","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"G. Kortsarz","year":"2006","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Gonzales, T. (ed.) Handbook of Approximation Algorithms and Metaheuristics. CRC Press, Boca Raton (2006)"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/978-3-540-72792-7_34","volume-title":"Integer Programming and Combinatorial Optimization","author":"R. Levi","year":"2007","unstructured":"Levi, R., Lodi, A., Sviridenko, M.I.: Approximation algorithms for the multi-item capacitated lot-sizing problem via flow-cover inequalities. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 454\u2013468. Springer, Heidelberg (2007)"},{"key":"14_CR15","unstructured":"Sharma, Y., Swamy, C., Williamson, D.P.: Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: SODA, pp. 1275\u20131284 (2007)"},{"issue":"3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"D.P. Williamson","year":"1995","unstructured":"Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica\u00a015(3), 435\u2013454 (1995)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-93980-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T16:10:55Z","timestamp":1551715855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-93980-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540939795","9783540939801"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-93980-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}