{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:14:24Z","timestamp":1761621264190},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_22","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T22:35:59Z","timestamp":1464129359000},"page":"262-274","source":"Crossref","is-referenced-by-count":13,"title":["An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\\epsilon $$ Capacity Violation"],"prefix":"10.1007","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[]},{"given":"Bartosz","family":"Rybicki","sequence":"additional","affiliation":[]},{"given":"Sumedha","family":"Uniyal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"issue":"2","key":"22_CR1","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.ejor.2014.10.011","volume":"242","author":"K Aardal","year":"2015","unstructured":"Aardal, K., van den Berg, P.L., Gijswijt, D., Li, S.: Approximation algorithms for hard capacitated $$k$$ -facility location problems. Eur. J. Oper. Res. 242(2), 358\u2013368 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"An, H.-C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. In: IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 256\u2013265. IEEE (2014)","DOI":"10.1109\/FOCS.2014.35"},{"issue":"3","key":"22_CR3","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for $$k$$ -median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Byrka, J., Fleszar, K., Rybicki, B., Spoerhase, J.: Bi-factor approximation algorithms for hard capacitated $$k$$ -median problems. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 722\u2013736. SIAM (2015)","DOI":"10.1137\/1.9781611973730.49"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$ -median, and positive correlation in budgeted optimization. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 737\u2013756. SIAM (2015)","DOI":"10.1137\/1.9781611973730.50"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Byrka, J., Rybicki, B., Uniyal, S.: An approximation algorithm for uniform capacitated $$k$$ -median problem with $$1+\\epsilon $$ capacity violation. CoRR abs\/1511.07494 (2015)","DOI":"10.1007\/978-3-319-33461-5_22"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the $$k$$ -median problem. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 1\u201310. ACM (1999)","DOI":"10.1145\/301250.301257"},{"key":"22_CR8","unstructured":"Chuzhoy, J., Rabani, Y.: Approximating $$k$$ -median with non-uniform capacities. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 952\u2013958. Society for Industrial and Applied Mathematics (2005)"},{"issue":"3","key":"22_CR9","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324\u2013360 (2006)","journal-title":"J. ACM"},{"key":"22_CR10","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 Symposium on Discrete Algorithms (SODA), pp. 696\u2013707. SIAM (2015)","DOI":"10.1137\/1.9781611973730.47"},{"key":"22_CR11","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), pp. 786\u2013796. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch56"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating $$k$$ -median via pseudo-approximation. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 901\u2013910. ACM (2013)","DOI":"10.1145\/2488608.2488723"}],"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-33461-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T19:46:54Z","timestamp":1567972014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}