{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T23:51:05Z","timestamp":1784850665346,"version":"3.55.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T00:00:00Z","timestamp":1389052800000},"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":[[2015,6]]},"DOI":"10.1007\/s00453-013-9862-4","type":"journal-article","created":{"date-parts":[[2014,1,6]],"date-time":"2014-01-06T11:42:27Z","timestamp":1389008547000},"page":"493-514","source":"Crossref","is-referenced-by-count":14,"title":["Approximability of Capacitated Network Design"],"prefix":"10.1007","volume":"72","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,1,7]]},"reference":[{"key":"9862_CR1","first-page":"585","volume-title":"Proceedings, IEEE Foundations of Computer Science (FOCS)","author":"M. Andrews","year":"2010","unstructured":"Andrews, M., Antonakopoulos, S., Zhang, L.: Minimum-cost network design with (Dis)economies of scale. In: Proceedings, IEEE Foundations of Computer Science (FOCS), pp. 585\u2013592 (2010)"},{"key":"9862_CR2","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s101070100284","volume":"92","author":"A. Atamturk","year":"2002","unstructured":"Atamturk, A.: On capacitated network design cut-set polyhedra. Math. Program. 92, 425\u2013437 (2002)","journal-title":"Math. Program."},{"key":"9862_CR3","first-page":"344","volume-title":"Proceedings, ACM Symposium on Theory of Computation (STOC)","author":"P. Berman","year":"1997","unstructured":"Berman, P., Coulston, C.: On-line algorithms for steiner tree problems (extended abstract). In: Proceedings, ACM Symposium on Theory of Computation (STOC), pp. 344\u2013353 (1997)"},{"key":"9862_CR4","first-page":"106","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"R.D. Carr","year":"2000","unstructured":"Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 106\u2013115 (2000)"},{"key":"9862_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Krishnaswamy, R., Li, S., Narayanan, S.: Capacitated network design in undirected graphs. Unpublished Manuscript as of April 2013","DOI":"10.1007\/978-3-642-40328-6_6"},{"issue":"2","key":"9862_CR6","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1109\/TNET.2004.826288","volume":"12","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Naor, J., Schieber, B.: Resource optimization in QoS multicast routing of real-time multimedia. IEEE\/ACM Trans. Netw. 12(2), 340\u2013348 (2004)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"5","key":"9862_CR7","doi-asserted-by":"crossref","first-page":"1772","DOI":"10.1137\/090750317","volume":"39","author":"C. Chekuri","year":"2009","unstructured":"Chekuri, C., Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Approximation algorithms for non-uniform buy-at-bulk network design. SIAM J. Comput. 39(5), 1772\u20131798 (2009)","journal-title":"SIAM J. Comput."},{"key":"9862_CR8","first-page":"105","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science","author":"J. Chuzhoy","year":"2008","unstructured":"Chuzhoy, J., Khanna, S.: Algorithms for single-source vertex connectivity. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 105\u2013114 (2008)"},{"issue":"1","key":"9862_CR9","doi-asserted-by":"crossref","first-page":"401","DOI":"10.4086\/toc.2012.v008a018","volume":"8","author":"J. Chuzhoy","year":"2012","unstructured":"Chuzhoy, J., Khanna, S.: An O(k 3logn)-approximation algorithm for vertex-connectivity survivable network design. Theory Comput. 8(1), 401\u2013413 (2012)","journal-title":"Theory Comput."},{"key":"9862_CR10","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Gupta, A., Naor, J., Sinha, A.: On the approximability of some network design problems. ACM Trans. Algorithms 4(2) (2008)","DOI":"10.1145\/1361192.1361200"},{"issue":"1","key":"9862_CR11","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/1077464.1077470","volume":"1","author":"G. Even","year":"2005","unstructured":"Even, G., Kortsarz, G., Slany, W.: On network design: fixed charge flows and the covering Steiner problem. ACM Trans. Algorithms 1(1), 74\u2013101 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"9862_CR12","first-page":"629","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"C.G. Fernandes","year":"1997","unstructured":"Fernandes, C.G.: A better approximation ratio for the minimum k-edge-connected spanning subgraph problem. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 629\u2013638 (1997)"},{"issue":"5","key":"9862_CR13","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1016\/j.jcss.2005.05.006","volume":"72","author":"L. Fleischer","year":"2006","unstructured":"Fleischer, L., Jain, K., Williamson, D.P.: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72(5), 838\u2013867 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9862_CR14","first-page":"223","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M.X. Goemans","year":"1994","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223\u2013232 (1994)"},{"key":"9862_CR15","unstructured":"Hajiaghayi, M.T., Khandekar, R., Kortsarz, G., Nutov, G.: Capacitated network design problems: hardness, approximation algorithms, and connections to group Steiner tree. Unpublished manuscript as of April 2013"},{"key":"9862_CR16","first-page":"585","volume-title":"Proceedings, ACM Symposium on Theory of Computation (STOC)","author":"E. Halperin","year":"2003","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings, ACM Symposium on Theory of Computation (STOC), pp. 585\u2013594 (2003)"},{"key":"9862_CR17","doi-asserted-by":"crossref","unstructured":"Hewitt, M., Nemhauser, G., Savelsbergh, M.W.P.: Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS J. Comput. 22(2) (2010)","DOI":"10.1287\/ijoc.1090.0348"},{"issue":"3","key":"9862_CR18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/net.3230190304","volume":"19","author":"D. Hochbaum","year":"1989","unstructured":"Hochbaum, D., Segev, A.: Analysis of a flow problem with fixed charges. Networks 19(3), 291\u2013312 (1989)","journal-title":"Networks"},{"issue":"1","key":"9862_CR19","doi-asserted-by":"crossref","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 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"9862_CR20","unstructured":"Karger, D.: Random sampling in graph optimization problems. Ph.D. Thesis, Stanford University (1994)"},{"key":"9862_CR21","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"G. Kortsarz","year":"2007","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. CRC Press, Boca Raton (2007)"},{"key":"9862_CR22","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9862_CR23","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization, Section II.6.4","author":"G. Nemhauser","year":"1988","unstructured":"Nemhauser, G., Wolsey, L.A.: Integer and Combinatorial Optimization, Section II.6.4. Wiley, New York (1988)"},{"key":"9862_CR24","first-page":"417","volume-title":"Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science","author":"Z. Nutov","year":"2009","unstructured":"Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. In: Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science, pp. 417\u2013426. IEEE Press, New York (2009)"},{"issue":"3","key":"9862_CR25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/net.10068","volume":"41","author":"F. Ortega","year":"2003","unstructured":"Ortega, F., Wolsey, L.A.: A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem. Networks 41(3), 143\u2013158 (2003)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9862-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9862-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9862-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T18:19:08Z","timestamp":1565029148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9862-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,7]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9862"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9862-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,7]]}}}