{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:11Z","timestamp":1759637591380},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,4,15]],"date-time":"2008-04-15T00:00:00Z","timestamp":1208217600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00453-008-9189-8","type":"journal-article","created":{"date-parts":[[2008,4,14]],"date-time":"2008-04-14T15:16:24Z","timestamp":1208186184000},"page":"529-549","source":"Crossref","is-referenced-by-count":5,"title":["Approximate k-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing"],"prefix":"10.1007","volume":"56","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","published-online":{"date-parts":[[2008,4,15]]},"reference":[{"issue":"3","key":"9189_CR1","doi-asserted-by":"crossref","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. 24(3), 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9189_CR2","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/1198513.1198522","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. ACM Transact. Algorithms 2(4), 640\u2013660 (2006)","journal-title":"ACM Transact. Algorithms"},{"issue":"5","key":"9189_CR3","doi-asserted-by":"crossref","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 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"9189_CR4","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-005-0693-1","volume":"107","author":"S. Arora","year":"2006","unstructured":"Arora, S., Karakostas, G.: A 2+\u03b5 approximation algorithm for the k-MST problem. Math. Program. 107(3), 491\u2013504 (2006)","journal-title":"Math. Program."},{"issue":"3","key":"9189_CR5","doi-asserted-by":"crossref","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. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"9189_CR6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1006\/jcss.1998.1605","volume":"58","author":"S. Arora","year":"1999","unstructured":"Arora, S., Karger, D.R., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58(1), 193\u2013210 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9189_CR7","doi-asserted-by":"crossref","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp.\u00a0553\u2013562 (2005)","DOI":"10.1145\/1060590.1060673"},{"issue":"2","key":"9189_CR8","doi-asserted-by":"crossref","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. J. Algorithms 34(2), 203\u2013221 (2000)","journal-title":"J. Algorithms"},{"issue":"1","key":"9189_CR9","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An O(log\u2009k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291\u2013301 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9189_CR10","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"B. Awerbuch","year":"1998","unstructured":"Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM J. Comput. 28(1), 254\u2013262 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"9189_CR11","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.tcs.2004.05.021","volume":"324","author":"B. Awerbuch","year":"2004","unstructured":"Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized Steiner problem. Theor. Comput. Sci. 324(2\u20133), 313\u2013324 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9189_CR12","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R. Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"key":"9189_CR13","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-line algorithms for Steiner tree problems (extended abstract). In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp.\u00a0344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"key":"9189_CR14","doi-asserted-by":"crossref","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. Program. 59, 413\u2013420 (1993)","journal-title":"Math. Program."},{"issue":"1","key":"9189_CR15","doi-asserted-by":"crossref","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. 58(1), 101\u2013108 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9189_CR16","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"issue":"1","key":"9189_CR17","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T.-Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"9189_CR18","unstructured":"Chawla, S., Gupta, A., R\u00e4cke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0102\u2013111 (2005)"},{"key":"9189_CR19","unstructured":"Chekuri, C., Even, G., Gupta, A., Segev, D.: Set connectivity problems in undirected graphs and the directed Steiner network problem. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0532\u2013541 (2008)"},{"issue":"2","key":"9189_CR20","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s10107-003-0479-2","volume":"100","author":"F.A. Chudak","year":"2004","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangian relaxation. Math. Program. 100(2), 411\u2013421 (2004)","journal-title":"Math. Program."},{"issue":"2","key":"9189_CR21","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.jda.2006.05.002","volume":"5","author":"R. Engelberg","year":"2007","unstructured":"Engelberg, R., K\u00f6nemann, J., Leonardi, S., Naor, J.: Cut problems in graphs with a budget constraint. J. Discrete Algorithms 5(2), 262\u2013279 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"9189_CR22","doi-asserted-by":"crossref","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. J. Algorithms 41(2), 174\u2013211 (2001)","journal-title":"J. Algorithms"},{"issue":"3","key":"9189_CR23","doi-asserted-by":"crossref","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 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"9189_CR24","doi-asserted-by":"crossref","unstructured":"Fleischer, L., K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G.: Simple cost sharing schemes for multi-commodity rent-or-buy and stochastic Steiner tree. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 663\u2013670 (2006)","DOI":"10.1145\/1132516.1132609"},{"issue":"4","key":"9189_CR25","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0167-6377(99)00045-0","volume":"25","author":"T. Fujito","year":"1999","unstructured":"Fujito, T.: On approximation of the submodular set cover problem. Oper. Res. Lett. 25(4), 169\u2013174 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9189_CR26","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R. Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J.\u00a0Algorithms 53(1), 55\u201384 (2004)","journal-title":"J.\u00a0Algorithms"},{"key":"9189_CR27","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9189_CR28","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 302\u2013309 (1996)","DOI":"10.1109\/SFCS.1996.548489"},{"key":"9189_CR29","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"issue":"2","key":"9189_CR30","doi-asserted-by":"crossref","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. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"9189_CR31","doi-asserted-by":"crossref","unstructured":"Golovin, D., Nagarajan, V., Singh, M.: Approximating the k-multicut problem. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete algorithm, pp.\u00a0621\u2013630 (2006)","DOI":"10.1145\/1109557.1109625"},{"key":"9189_CR32","doi-asserted-by":"crossref","unstructured":"Gupta, A., P\u00e1l, M.: Stochastic Steiner trees without a root. In: Proceedings on the 32nd International Colloquium on Automata, Languages and Programming, pp. 1051\u20131063 (2005)","DOI":"10.1007\/11523468_85"},{"key":"9189_CR33","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., P\u00e1l, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the 44th Annual Symposium on Foundations of Computer Science, pp. 606\u2013615 (2003)","DOI":"10.1109\/SFCS.2003.1238233"},{"key":"9189_CR34","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hajiaghayi, M., Nagarajan, V., Ravi, R.: Dial a ride from k-forest. In: Proceedings of the 15th Annual European Symposium on Algorithms, pp. 241\u2013252 (2007)","DOI":"10.1007\/978-3-540-75520-3_23"},{"key":"9189_CR35","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: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"issue":"3","key":"9189_CR36","doi-asserted-by":"crossref","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. Math. Program. 92(3), 509\u2013535 (2002)","journal-title":"Math. Program."},{"issue":"2","key":"9189_CR37","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1137\/S0097539703426775","volume":"33","author":"R. Hassin","year":"2004","unstructured":"Hassin, R., Levin, A.: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM J. Comput. 33(2), 261\u2013268 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9189_CR38","doi-asserted-by":"crossref","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 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"9189_CR39","volume-title":"The Computational Complexity of Machine Learning","author":"M.J. Kearns","year":"1990","unstructured":"Kearns, M.J.: The Computational Complexity of Machine Learning. MIT Press, Cambridge (1990). The approximation guarantee of the partial cover algorithm we refer to is stated in Theorem 5.15"},{"key":"9189_CR40","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Parekh, O., Segev, D.: A unified approach to approximating partial covering problems. In: Proceedings of the 14th Annual European Symposium on Algorithms, pp. 468\u2013479 (2006)","DOI":"10.1007\/11841036_43"},{"key":"9189_CR41","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Peleg, D.: On choosing a dense subgraph. In: Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 692\u2013701 (1993)","DOI":"10.1109\/SFCS.1993.366818"},{"issue":"1\u20133","key":"9189_CR42","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/j.tcs.2006.09.018","volume":"369","author":"A. Levin","year":"2006","unstructured":"Levin, A., Segev, D.: Partial multicuts in trees. Theor. Comput. Sci. 369(1\u20133), 384\u2013395 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9189_CR43","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"4","key":"9189_CR44","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"9189_CR45","unstructured":"Nagarajan, V.: Personal communication, January 2008"},{"issue":"3","key":"9189_CR46","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s00453-006-0191-8","volume":"47","author":"J. Naor","year":"2007","unstructured":"Naor, J., Shachnai, H., Tamir, T.: Real-time scheduling with a budget. Algorithmica 47(3), 343\u2013364 (2007)","journal-title":"Algorithmica"},{"issue":"3","key":"9189_CR47","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9189_CR48","unstructured":"Rajagopalan, S., Vazirani, V.V.: Logarithmic approximation of minimum weight k-trees. Unpublished manuscript (1995)"},{"key":"9189_CR49","doi-asserted-by":"crossref","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem (extended abstract). In: Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, pp. 66\u201375 (1996)","DOI":"10.1007\/3-540-61422-2_121"},{"issue":"2","key":"9189_CR50","doi-asserted-by":"crossref","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\u2014short or small. SIAM J. Discrete Math. 9(2), 178\u2013200 (1996)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"9189_CR51","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P. Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett. 64(5), 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9189-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9189-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9189-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:02Z","timestamp":1559137502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9189-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,15]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9189"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9189-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,15]]}}}