{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:07:57Z","timestamp":1725552477548},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642121999"},{"type":"electronic","value":"9783642122002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12200-2_45","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T13:53:05Z","timestamp":1271857985000},"page":"515-526","source":"Crossref","is-referenced-by-count":7,"title":["Prize-Collecting Steiner Networks via Iterative Rounding"],"prefix":"10.1007","author":[{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"first","affiliation":[]},{"given":"Arefeh A.","family":"Nasri","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: FOCS 1997, p. 542 (1997)","DOI":"10.1109\/SFCS.1997.646143"},{"key":"45_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":"45_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded directed network design. In: STOC 2008, pp. 769\u2013778 (2008)","DOI":"10.1145\/1374376.1374486"},{"key":"45_CR4","unstructured":"Becchetti, L., Konemann, J., Leonardi, S., Pal, M.: Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy. In: SODA 2005, pp. 375\u2013384 (2005)"},{"key":"45_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.: A note on the prize collecting traveling salesman problem. Math. Prog.\u00a059, 413\u2013420 (1993)","journal-title":"Math. Prog."},{"key":"45_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45535-3_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"F.A. Chudak","year":"2001","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-MSTs and k-Steiner trees via the primal-dual method and lagrangean relaxation. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 60\u201370. Springer, Heidelberg (2001)"},{"key":"45_CR7","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, 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"45_CR8","unstructured":"Gupta, A., K\u00f6nemann, J., Leonardi, S., Ravi, R., Sch\u00e4fer, G.: An efficient cost-sharing mechanism for the prize-collecting steiner forest problem. In: SODA 2007, pp. 1153\u20131162 (2007)"},{"key":"45_CR9","unstructured":"Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: FOCS 2003, p. 606 (2003)"},{"key":"45_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.ipl.2007.12.010","volume":"107","author":"S. Gutner","year":"2008","unstructured":"Gutner, S.: Elementary approximation algorithms for prize collecting Steiner tree problems. Inf. Process. Lett.\u00a0107, 39\u201344 (2008)","journal-title":"Inf. Process. Lett."},{"key":"45_CR11","unstructured":"M.\u00a0Hajiaghayi, Designing minimum total cost networks using iterative rounding approximation methods. Pending patent with USPTO of application number 12\/315,657 (July 2008)"},{"key":"45_CR12","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 2006, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"45_CR13","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":"45_CR14","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM\u00a048, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"45_CR15","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: SODA 2000, pp. 760\u2013769 (2000)"},{"key":"45_CR16","unstructured":"Karger, D.R., Minkoff, M.: Building steiner trees with incomplete global knowledge. In: FOCS 2001, p. 613 (2001)"},{"key":"45_CR17","unstructured":"Kumar, A., Gupta, A., Roughgarden, T.: A constant-factor approximation algorithm for the multicommodity. In: FOCS 2002, p. 333 (2002)"},{"key":"45_CR18","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Naor, J.S., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. In: STOC 2007, pp. 651\u2013660 (2007)","DOI":"10.1145\/1250790.1250886"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. In: STOC 2008, pp. 759\u2013768 (2008)","DOI":"10.1145\/1374376.1374485"},{"key":"45_CR20","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1137\/S1052623497321432","volume":"11","author":"F.S. Salman","year":"2000","unstructured":"Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the single-sink link-installation problem in network design. SIAM J. Optim.\u00a011, 595\u2013610 (2000)","journal-title":"SIAM J. Optim."},{"key":"45_CR21","unstructured":"Sharma, Y., Swamy, C., Williamson, D.P.: Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: SODA 2007, pp. 1275\u20131284 (2007)"},{"key":"45_CR22","unstructured":"Konemann, J., Grandoni, F., Rothvoss, T., Qian, J., Schaefer, G., Swamy, C., Williamson, D.P.: An iterated rounding 3-approximation algorithm for prize-collecting Steiner forest (2009) (unpublished manuscript)"},{"key":"45_CR23","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC 2007, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"}],"container-title":["Lecture Notes in Computer Science","LATIN 2010: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12200-2_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:05:37Z","timestamp":1619784337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}