{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T11:14:04Z","timestamp":1764587644786},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_6","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"71-80","source":"Crossref","is-referenced-by-count":9,"title":["Capacitated Network Design on Undirected Graphs"],"prefix":"10.1007","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shi","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srivatsan","family":"Narayanan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644031","volume":"6","author":"K. Andreev","year":"2009","unstructured":"Andreev, K., Garrod, C., Golovin, D., Maggs, B., Meyerson, A.: Simultaneous source location. Trans. on Algorithms (TALG)\u00a06(1), 1\u201317 (2009)","journal-title":"Trans. on Algorithms (TALG)"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/jagm.2001.1203","volume":"42","author":"K. Arata","year":"2002","unstructured":"Arata, K., Iwata, S., Makino, K., Fujishige, S.: Locating sources to meet flow demands in undirected networks. J. of Algorithms\u00a042, 54\u201368 (2002)","journal-title":"J. of Algorithms"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-642-20807-2_7","volume-title":"Integer Programming and Combinatoral Optimization","author":"D. Chakrabarty","year":"2011","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of capacitated network design. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 78\u201391. Springer, Heidelberg (2011)"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Design networks with bounded pairwise distance. In: ACM Symp. on Theory of Computing, STOC (1999)","DOI":"10.1145\/301250.301447"},{"issue":"1","key":"6_CR5","doi-asserted-by":"publisher","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. Trans. on Algorithms (TALG)\u00a01(1), 74\u2013101 (2005)","journal-title":"Trans. on Algorithms (TALG)"},{"key":"6_CR6","unstructured":"Feige, U.: Vertex cover is hardest to approximate on regular graphs, Tech. report, Weizmann Institute (2004)"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1006\/jcss.1998.1592","volume":"57","author":"T. Hagerup","year":"1998","unstructured":"Hagerup, T., Katajainen, J., Nishimura, N., Ragde, P.: Characterizations of multiterminal flow networks and computing flows in networks of bounded treewidth. Journal of Computer and System Sciences (JCSS)\u00a057, 366\u2013375 (1998)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"6_CR8","unstructured":"Hajiaghayi, M.T., Khandekar, R., Kortsarz, G., Nutov, Z.: Capacitated Network Design problems: Hardness, approximation algorithms, and connections to group Steiner tree (2011), \n                    \n                      http:\/\/arxiv.org\/pdf\/1108.1176.pdf"},{"issue":"1","key":"6_CR9","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":"6_CR10","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: Proceedings of FOCS (2003)"},{"issue":"3","key":"6_CR11","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1016\/j.jda.2006.12.010","volume":"6","author":"G. Kortsarz","year":"2008","unstructured":"Kortsarz, G., Nutov, Z.: A note on two source location problems. J. of Discrete Algorithms\u00a06(3), 520\u2013525 (2008)","journal-title":"J. of Discrete Algorithms"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Labbe, M., Peeters, D., Thisse, J.-F.: Location on networks. In: Handbook in OR and MS, vol.\u00a08, pp. 551\u2013624 (1995)","DOI":"10.1016\/S0927-0507(05)80111-2"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/11682462_70","volume-title":"LATIN 2006: Theoretical Informatics","author":"M. Sakashita","year":"2006","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimum cost source location problems with flow requirements. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 769\u2013780. Springer, Heidelberg (2006)"},{"key":"6_CR14","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Location problems on undirected flow networks. IEICE Trans. E(73), 1989\u20131993 (1990)"},{"key":"6_CR15","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Some covering problems in location theory on flow networks. IEICE Trans. E(75), 678\u2013683 (1992)"},{"issue":"4","key":"6_CR16","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L. Wolsey","year":"1982","unstructured":"Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:41:08Z","timestamp":1558028468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}