{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T07:47:00Z","timestamp":1759132020714},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_7","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"78-91","source":"Crossref","is-referenced-by-count":12,"title":["Approximability of Capacitated Network Design"],"prefix":"10.1007","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","first-page":"585","volume-title":"Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science","author":"M. Andrews","year":"2010","unstructured":"Andrews, M., Antonakopoulos, S., Zhang, L.: Minimum-Cost Network Design with (Dis)economies of Scale. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 585\u2013592. IEEE, Los Alamitos (2010)"},{"issue":"3","key":"7_CR2","doi-asserted-by":"publisher","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\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"7_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations. J. Comp. Sys. Sci.\u00a054(2), 317\u2013331 (1997)","journal-title":"J. Comp. Sys. Sci."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-Line Algorithms for Steiner Tree Problems. In: Proceedings, ACM Symposium on Theory of Computation (STOC), pp. 344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"key":"7_CR5","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of Capacitated Network Design. Technical Report. arXiv:1009.5734"},{"key":"7_CR6","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)"},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","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.\u00a012(2), 340\u2013348 (2004)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. In: Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pp. 677\u2013686 (2006)","DOI":"10.1109\/FOCS.2006.15"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Gupta, A., Naor, J., Sinha, A.: On the approximability of some network design problems. ACM Transactions on Algorithms\u00a04(2) (2008)","DOI":"10.1145\/1361192.1361200"},{"key":"7_CR10","doi-asserted-by":"crossref","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)","DOI":"10.1109\/FOCS.2008.63"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Khanna, S.: An O(k 3 logn)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 437\u2013441 (2009)","DOI":"10.1109\/FOCS.2009.38"},{"key":"7_CR12","unstructured":"Fernandes, C.G.: A better approximation ratio for the minimum k-edge-connected spanning subgraph problem. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 629\u2013638 (1997)"},{"issue":"5","key":"7_CR13","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a072(5), 838\u2013867 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR14","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: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223\u2013232 (1994)"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1287\/ijoc.1090.0348","volume":"22","author":"M. Hewitt","year":"2010","unstructured":"Hewitt, M., Nemhauser, G.L., Savelsbergh, M.W.P.: Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS Journal on Computing\u00a022(2), 314\u2013325 (2010)","journal-title":"INFORMS Journal on Computing"},{"issue":"1","key":"7_CR16","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(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"7_CR17","unstructured":"Karger, D.: Random Sampling in Graph Optimization Problems. Ph.D. Thesis, Stanford University (1994)"},{"key":"7_CR18","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":"7_CR19","doi-asserted-by":"publisher","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":"7_CR20","first-page":"417","volume-title":"Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Z. Nutov","year":"2009","unstructured":"Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. In: Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 417\u2013426. IEEE, Los Alamitos (2009)"},{"issue":"3","key":"7_CR21","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM Journal of Computing\u00a027(3), 763\u2013803 (1998)","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:16:03Z","timestamp":1560284163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}