{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T05:25:49Z","timestamp":1740029149172,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"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_44","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T13:53:05Z","timestamp":1271857985000},"page":"503-514","source":"Crossref","is-referenced-by-count":0,"title":["Euclidean Prize-Collecting Steiner Forest"],"prefix":"10.1007","author":[{"given":"MohammadHossein","family":"Bateni","sequence":"first","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. In: FOCS (2009)","DOI":"10.1109\/FOCS.2009.39"},{"key":"44_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM\u00a045, 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"44_CR3","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":"44_CR4","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M.: Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. In: SODA, pp. 805\u2013814 (2009)","DOI":"10.1137\/1.9781611973068.88"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M.: Euclidean prize-collecting Steiner forest, CoRR, abs\/0912.1137 (2009)","DOI":"10.1007\/978-3-642-12200-2_44"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth, CoRR, abs\/0911.5143 (2009)","DOI":"10.1145\/1806689.1806720"},{"key":"44_CR7","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett.\u00a032, 171\u2013176 (1989)","journal-title":"Inf. Proc. Lett."},{"key":"44_CR8","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":"44_CR9","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, 101\u2013108 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0166-218X(03)00439-6","volume":"136","author":"P. Bonsma","year":"2004","unstructured":"Bonsma, P.: Sparsest cuts and concurrent flows in product graphs. Discrete Appl. Math.\u00a0136, 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for Euclidean Steiner forest. In: FOCS, pp. 115\u2013124 (2008), http:\/\/www.math.uwaterloo.ca\/~glencora\/downloads\/Steiner-forest-FOCS-update.pdf","DOI":"10.1109\/FOCS.2008.59"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs. In: FOCS, pp. 71\u201380 (2004)","DOI":"10.1109\/FOCS.2004.27"},{"key":"44_CR13","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/1060590.1060618","volume-title":"STOC","author":"C. Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: STOC, pp. 183\u2013192. ACM, New York (2005)"},{"key":"44_CR14","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":"44_CR15","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, 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"44_CR16","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: STOC, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"44_CR17","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":"44_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-540-75520-3_23","volume-title":"Algorithms \u2013 ESA 2007","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Hajiaghayi, M., Nagarajan, V., Ravi, R.: Dial a ride from k-forest. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 241\u2013252. Springer, Heidelberg (2007)"},{"key":"44_CR19","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: SODA, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"44_CR20","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Nasri, A.: Prize-collecting Steiner networks via iterative rounding. In: LATIN (to appear, 2010)","DOI":"10.1007\/978-3-642-12200-2_45"},{"key":"44_CR21","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":"44_CR22","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: SODA, pp. 760\u2013769 (2000)"},{"key":"44_CR23","first-page":"184","volume-title":"SODA","author":"P. Kolman","year":"2002","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: SODA, pp. 184\u2013193. Society for Industrial and Applied Mathematics, Philadelphia (2002)"},{"key":"44_CR24","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM\u00a046, 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"44_CR25","doi-asserted-by":"publisher","first-page":"1460","DOI":"10.1109\/TIT.2008.917663","volume":"54","author":"R. Madan","year":"2008","unstructured":"Madan, R., Shah, D., Leveque, O.: Product multicommodity flow in wireless networks. IEEE Trans. Info. Theory\u00a054, 1460\u20131476 (2008)","journal-title":"IEEE Trans. Info. Theory"},{"key":"44_CR26","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.C. Mitchell","year":"1995","unstructured":"Mitchell, J.C.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput.\u00a028, 1298\u20131309 (1995)","journal-title":"SIAM J. Comput."},{"key":"44_CR27","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., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees - short or small. SIAM J. Discrete Math.\u00a09, 178\u2013200 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"44_CR28","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math.\u00a019, 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"44_CR29","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. Opt.\u00a011, 595\u2013610 (2000)","journal-title":"SIAM J. Opt."},{"key":"44_CR30","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)"}],"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_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T03:12:40Z","timestamp":1740021160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}