{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:57Z","timestamp":1759637937473},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,8,13]],"date-time":"2014-08-13T00:00:00Z","timestamp":1407888000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s10878-014-9774-5","type":"journal-article","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T11:11:18Z","timestamp":1407841878000},"page":"669-685","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Improved approximations for buy-at-bulk and shallow-light $$k$$ k -Steiner trees and $$(k,2)$$ ( k , 2 ) -subgraph"],"prefix":"10.1007","volume":"31","author":[{"given":"M. Reza","family":"Khani","sequence":"first","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,8,13]]},"reference":[{"key":"9774_CR1","doi-asserted-by":"crossref","unstructured":"Andrews M (2004) Hardness of buy-at-bulk network design. Proceedings of IEEE FOCS, pp 115\u2013124.","DOI":"10.1109\/FOCS.2004.32"},{"issue":"2","key":"9774_CR2","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s00453-002-0968-3","volume":"32","author":"M Andrews","year":"2002","unstructured":"Andrews M, Zhang L (2002) Approximation algorithms for access network design. Algorithmica 32(2):197\u2013215","journal-title":"Algorithmica"},{"issue":"1","key":"9774_CR3","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1287\/moor.1110.0484","volume":"36","author":"S Antonakopoulos","year":"2011","unstructured":"Antonakopoulos S, Chekuri C, Shepherd B, Zhang L (2011) Buy-at-bulk network design with protection. Mathe Oper Res 36(1):71\u201387","journal-title":"Mathe Oper Res"},{"key":"9774_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Azar Y. (1997) Buy-at-bulk network design, In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS \u201997), pp 542\u2013547.","DOI":"10.1109\/SFCS.1997.646143"},{"issue":"1","key":"9774_CR5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"B Awerbuch","year":"1999","unstructured":"Awerbuch B, Azar Y, Blum A, Vempala S (1999) New approximation guarantees for minimum-weight $$k$$ k -trees and prize-collecting salesmen. SIAM J Comput 28(1):254\u2013262","journal-title":"SIAM J Comput"},{"key":"9774_CR6","unstructured":"Bartal Y (1997) On approximating arbitrary metrics by tree metrics. In: Proceedings of ACM STOC, pp 161\u2013168."},{"issue":"1","key":"9774_CR7","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(99)00130-9","volume":"250","author":"J Bar-Ilan","year":"2001","unstructured":"Bar-Ilan J, Kortsarz G, Peleg D (2001) Generalized submodular cover problems and applications. Theor Comput Sci 250(1):179\u2013200","journal-title":"Theor Comput Sci"},{"issue":"3","key":"9774_CR8","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s00453-011-9610-6","volume":"65","author":"M Bateni","year":"2013","unstructured":"Bateni M, Chuzhoy J (2013) Approximation algorithms for the directed $$k$$ k -Tour and $$k$$ k -Stroll problems. Algorithmica 65(3):545\u2013561","journal-title":"Algorithmica"},{"key":"9774_CR9","doi-asserted-by":"crossref","unstructured":"Bhaskara A, Charikar M, Chlamtac E, Feige U, Vijayaraghavan A (2010) Detecting high log-densities: an $$O(n^{1\/4})$$ O ( n 1 \/ 4 ) -approximation for densest $$k$$ k -subgraph. In: Proceedings of ACM Symposium on the Theory of Computing (STOC), pp 201\u2013210.","DOI":"10.1145\/1806689.1806719"},{"issue":"1","key":"9774_CR10","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 (1999) A constant-factor approximation algorithm for the $$k$$ k -MST problem. J Comput Syst Sci 58(1):101\u2013108","journal-title":"J Comput Syst Sci"},{"key":"9774_CR11","doi-asserted-by":"crossref","unstructured":"Chekuri C, Kumar A (2004) Maximum coverage problem with group budget constraints and applications. In: Approximation algorithms for combinatorial optimization, pp 72\u201383","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"9774_CR12","unstructured":"Chekuri C, Khanna S, Naor J (2001) A deterministic approximation algorithm for the cost-distance problem. Short paper in Proceedings of ACM-SIAM SODA, pp 232\u2013233."},{"key":"9774_CR13","unstructured":"Chekuri C, Hajiaghayi M, Kortsarz G, Salavatipour M (2006) Approximation algorithms for non-uniform buy-at-bulk network design problems. In: Proceedings of IEEE FOCS, pp 677\u2013686."},{"issue":"5","key":"9774_CR14","doi-asserted-by":"crossref","first-page":"1772","DOI":"10.1137\/090750317","volume":"39","author":"C Chekuri","year":"2009","unstructured":"Chekuri C, Hajiaghayi M, Kortsarz G, Salavatipour M (2009) Approximation algorithms for non-uniform buy-at-bulk network design. SIAM J Comput 39(5):1772\u20131798","journal-title":"SIAM J Comput"},{"key":"9774_CR15","unstructured":"Chuzhoy J, Gupta A, Naor S, Sinha A (2005) On the approximability of some network design problems. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp 943\u2013951. Society for Industrial and Applied Mathematics."},{"issue":"4","key":"9774_CR16","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/j.orl.2003.11.010","volume":"32","author":"G Even","year":"2004","unstructured":"Even G, Garg N, Konemann J, Ravi R, Sinha A (2004) Covering graphs using trees and stars. Oper Res Lett 32(4):309\u2013315","journal-title":"Oper Res Lett"},{"issue":"3","key":"9774_CR17","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol J, Rao S, Talwar K (2004) A tight bound on approximating arbitrary metrics by tree metrics. J Comput Syst Sci 69(3):485\u2013497","journal-title":"J Comput Syst Sci"},{"key":"9774_CR18","doi-asserted-by":"crossref","unstructured":"Garg N (2005) Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC), pp 396\u2013402.","DOI":"10.1145\/1060590.1060650"},{"key":"9774_CR19","doi-asserted-by":"crossref","unstructured":"Guha S, Meyerson A, Munagala K (2009) A constant factor approximation for the single sink edge installation problem. SIAM J Comput 38(6):2426\u20132442","DOI":"10.1137\/050643635"},{"key":"9774_CR20","doi-asserted-by":"crossref","unstructured":"Gupta A, Krishnaswamy R, Ravi R (2010) Tree embeddings for two-edge-connected network design. In: Proceedings of of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1521\u20131538, SODA.","DOI":"10.1137\/1.9781611973075.124"},{"key":"9774_CR21","doi-asserted-by":"crossref","unstructured":"Gupta A, Kumar A, Pal M, Roughgarden T (2003) Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the 44rd Symposium on Foundations of Computer Science (FOCS \u201903), pp 606\u2013615. IEEE.","DOI":"10.1109\/SFCS.2003.1238233"},{"key":"9774_CR22","doi-asserted-by":"crossref","unstructured":"Gupta A, Kumar A, Roughgarden T. Simpler and better approximation algorithms for network design, In Proceedings of the thirty-fifth ACM symposium on Theory of computing (STOC \u201903), pp 365\u2013372. ACM.","DOI":"10.1145\/780542.780597"},{"issue":"1","key":"9774_CR23","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s00453-007-9013-x","volume":"53","author":"MT Hajiaghayi","year":"2009","unstructured":"Hajiaghayi MT, Kortsarz G, Salavatipour MR (2009) Approximating buy-at-bulk and shallow-light $$k$$ k -steiner tree. Algorithmica 53(1):89\u2013103","journal-title":"Algorithmica"},{"issue":"1","key":"9774_CR24","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17(1):36\u201342","journal-title":"Math Oper Res"},{"key":"9774_CR25","first-page":"175","volume-title":"Minimum restricted diameter spanning trees","author":"R Hassin","year":"2002","unstructured":"Hassin R, Levin A (2002) Minimum restricted diameter spanning trees. Springer, Berlin, pp 175\u2013184"},{"issue":"1","key":"9774_CR26","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain K (2001) A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21(1):39\u201360","journal-title":"Combinatorica"},{"key":"9774_CR27","doi-asserted-by":"crossref","unstructured":"Khani MR, Salavatipour MR (2011) Approximation algorithms for min-max tree cover and bounded tree cover problems. In: Proceedings of APPROX.","DOI":"10.1007\/978-3-642-22935-0_26"},{"key":"9774_CR28","unstructured":"Kortsarz G, Nutov Z (2009) Approximating some network design problems with vertex costs. In: Proceedings APPROX-RANDOM, pp 231\u2013243."},{"key":"9774_CR29","doi-asserted-by":"crossref","unstructured":"Kumar A, Gupta A, Roughgarden T (2002) A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS \u201902), pp 333\u2013342. IEEE.","DOI":"10.1109\/SFCS.2002.1181956"},{"key":"9774_CR30","doi-asserted-by":"crossref","unstructured":"Lau L, Naor S, Salavatipour MR, Singh M (2009) Survivable network design with degree or order constraints. SIAM J Comput 39(3):1062\u20131087 Special issue for selected papers of STOC.","DOI":"10.1137\/070700620"},{"key":"9774_CR31","doi-asserted-by":"crossref","unstructured":"Marathe MV, Ravi R, Sundaram R, Ravi SS, Rosenkrantz D, Hunt HB (1998) Bicriteria network design. J Algorithms 28(1):142\u2013171","DOI":"10.1006\/jagm.1998.0930"},{"key":"9774_CR32","doi-asserted-by":"crossref","unstructured":"Meyerson A, Munagala K, Plotkin S (2008) Cost-Distance: Two Metric Network Design. SIAM J. on Computing, 2648\u20131659.","DOI":"10.1137\/050629665"},{"issue":"2","key":"9774_CR33","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R Ravi","year":"1996","unstructured":"Ravi R, Sundaram R, Marathe MV, Rosenkrants DJ, Ravi SS (1996) Spanning trees short or small. SIAM J Discret Math 9(2):178\u2013200","journal-title":"SIAM J Discret Math"},{"issue":"3","key":"9774_CR34","doi-asserted-by":"crossref","first-page":"1089","DOI":"10.1137\/080729918","volume":"25","author":"MA Safari","year":"2011","unstructured":"Safari MA, Salavatipour MR (2011) A constant factor approximation for minimum $$\\lambda $$ \u03bb -edge-connected $$k$$ k -subgraph with metric costs. SIAM J Discrete Math 25(3):1089\u20131102","journal-title":"SIAM J Discrete Math"},{"issue":"3","key":"9774_CR35","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1137\/S1052623497321432","volume":"11","author":"FS Salman","year":"2000","unstructured":"Salman FS, Cheriyan J, Ravi R, Subramanian S (2000) Approximating the single-sink link-installation problem in network design. SIAM J Optim 11(3):595\u2013610","journal-title":"SIAM J Optim"},{"key":"9774_CR36","volume-title":"Combinatorial optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin"},{"key":"9774_CR37","doi-asserted-by":"crossref","unstructured":"Seymour PD (1981) Nowhere-zero 6-flows. J Comb Theory B 30(2):130\u2013135","DOI":"10.1016\/0095-8956(81)90058-7"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9774-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9774-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9774-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:23:24Z","timestamp":1559276604000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9774-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,13]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9774"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9774-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,13]]}}}