{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:32Z","timestamp":1774421312206,"version":"3.50.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319592497","type":"print"},{"value":"9783319592503","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_11","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"123-135","source":"Crossref","is-referenced-by-count":7,"title":["The Heterogeneous Capacitated k-Center Problem"],"prefix":"10.1007","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-319-07557-0_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"H-C An","year":"2014","unstructured":"An, H.-C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated k-center. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 52\u201363. Springer, Cham (2014). doi: 10.1007\/978-3-319-07557-0_5"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"An, H., Singh, M., Svensson, O.: Lp-based algorithms for capacitated facility location. In: 55th IEEE FOCS 2014, Philadelphia, PA, USA, 18\u201321 October 2014, pp. 256\u2013265 (2014)","DOI":"10.1109\/FOCS.2014.35"},{"issue":"3","key":"11_CR3","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/2229163.2229168","volume":"8","author":"A Asadpour","year":"2012","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. ACM Trans. Algorithms 8(3), 24 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"11_CR4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01193837","volume":"47","author":"L Babel","year":"1998","unstructured":"Babel, L., Kellerer, H., Kotov, V.: Thek-partitioning problem. Math. Meth. OR 47(1), 59\u201382 (1998)","journal-title":"Math. Meth. OR"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-33090-2_13","volume-title":"Algorithms \u2013 ESA 2012","author":"M Bansal","year":"2012","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 133\u2013144. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-33090-2_13"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The santa claus problem. In: Proceedings of the 38th Annual ACM STOC 2006, pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"issue":"3","key":"11_CR7","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1006\/jagm.1993.1047","volume":"15","author":"J Bar-Ilan","year":"1993","unstructured":"Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15(3), 385\u2013415 (1993)","journal-title":"J. Algorithms"},{"key":"11_CR8","unstructured":"Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the Eleventh Annual ACM-SIAM SODA, San Francisco, CA, USA, 9\u201311 January 2000, pp. 106\u2013115 (2000)"},{"key":"11_CR9","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. 6655, pp. 78\u201391. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20807-2_7"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: 50th Annual IEEE FOCS 2009, Atlanta, Georgia, USA, 25\u201327 October 2009, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"key":"11_CR11","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. In: 43rd ICALP 2016, pp. 67:1\u201367:15 (2016)"},{"key":"11_CR12","unstructured":"Chakrabarty, D., Krishnaswamy, R., Kumar, A.: The heterogeneous capacitated $$k$$ -center problem. CoRR, abs\/1611.07414 (2016)"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for k-centers with non-uniform hard capacities. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20\u201323 October 2012, pp. 273\u2013282 (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"11_CR14","unstructured":"Demirci, H.G., Li, S.: Constant approximation for capacitated k-median with (1+epsilon)-capacity violation. In: 43rd ICALP 2016, pp. 73:1\u201373:14 (2016)"},{"key":"11_CR15","unstructured":"Feige, U.: On allocations that maximize fairness. In: Proceedings of the Nineteenth Annual ACM-SIAM SODA 2008, pp. 287\u2013293 (2008)"},{"issue":"2","key":"11_CR16","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR17","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1287\/moor.2015.0729","volume":"41","author":"IL G\u00f8rtz","year":"2016","unstructured":"G\u00f8rtz, I.L., Molinaro, M., Nagarajan, V., Ravi, R.: Capacitated vehicle routing with nonuniform speeds. Math. Oper. Res. 41(1), 318\u2013331 (2016)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"11_CR18","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0306-4379(01)00008-4","volume":"26","author":"S Guha","year":"2001","unstructured":"Guha, S., Rastogi, R., Shim, K.: Cure: an efficient clustering algorithm for large databases. Inf. Syst. 26(1), 35\u201358 (2001)","journal-title":"Inf. Syst."},{"issue":"2","key":"11_CR19","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: Scheduling in bandwidth constrained tree networks. In: Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, 13\u201315 June 2015, pp. 171\u2013180 (2015)","DOI":"10.1145\/2755573.2755576"},{"issue":"5","key":"11_CR21","first-page":"359","volume":"39","author":"H Kellerer","year":"2011","unstructured":"Kellerer, H., Kotov, V.: A 3\/2-approximation algorithm for 3\/2-partitioning. Oper. Res. Lett. 39(5), 359\u2013362 (2011)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"11_CR22","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Sussmann, Y.J.: The capacitated K-center problem. SIAM J. Discrete Math. 13(3), 403\u2013418 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"11_CR23","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"FT Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Li, S.: On uniform capacitated k-median beyond the natural LP relaxation. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM SODA 2015, pp. 696\u2013707 (2015)","DOI":"10.1137\/1.9781611973730.47"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Li, S.: Approximating capacitated $$k$$ -median with (1 + $$\\epsilon )k$$ open facilities. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10\u201312 January 2016, pp. 786\u2013796 (2016)","DOI":"10.1137\/1.9781611974331.ch56"},{"issue":"2","key":"11_CR26","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1006\/jagm.1997.0922","volume":"27","author":"R Lupton","year":"1998","unstructured":"Lupton, R., Maley, F.M., Young, N.E.: Data collection for the sloan digital sky survey - a network-flow heuristic. J. Algorithms 27(2), 339\u2013356 (1998)","journal-title":"J. Algorithms"},{"issue":"5","key":"11_CR27","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/359581.359591","volume":"20","author":"HL Morgan","year":"1977","unstructured":"Morgan, H.L., Levin, K.D.: Optimal program and data locations in computer networks. Commun. ACM 20(5), 315\u2013322 (1977)","journal-title":"Commun. ACM"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Murthy, K., Kam, J.B., Krishnamoorthy, M.S.: An approximation algorithm to the file allocation problem in computer networks. In: PODS (1983)","DOI":"10.1145\/588058.588087"},{"issue":"2","key":"11_CR29","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2818695","volume":"12","author":"L Pol\u00e1cek","year":"2016","unstructured":"Pol\u00e1cek, L., Svensson, O.: Quasi-polynomial local search for restricted max-min fair allocation. ACM Trans. Algorithms 12(2), 13 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Qiu, Z., Stein, C., Zhong, Y.: Minimizing the total weighted completion time of coflows in datacenter networks. In: Proceedings of the 27th ACM SPAA 2015, pp. 294\u2013303 (2015)","DOI":"10.1145\/2755573.2755592"},{"key":"11_CR31","unstructured":"Saha, B., Srinivasan, A.: A new approximation technique for resource-allocation problems. In: Innovations in Computer Science, ICS 2010, pp. 342\u2013357 (2010)"},{"key":"11_CR32","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/j.cor.2014.05.023","volume":"62","author":"G Sen","year":"2015","unstructured":"Sen, G., Krishnamoorthy, M., Rangaraj, N., Narayanan, V.: Exact approaches for static data segment allocation problem in an information network. Comput. Oper. Res. 62, 282\u2013295 (2015)","journal-title":"Comput. Oper. Res."},{"key":"11_CR33","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993)","journal-title":"Math. Program."},{"key":"11_CR34","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/j.disopt.2005.06.005","volume":"2","author":"GJ Woeginger","year":"2005","unstructured":"Woeginger, G.J.: A comment on scheduling two parallel machines with capacity constraints. Discrete Optim. 2, 269\u2013272 (2005)","journal-title":"Discrete Optim."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,8]],"date-time":"2020-10-08T08:45:48Z","timestamp":1602146748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}