{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T23:34:54Z","timestamp":1772580894341,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1813053"],"award-info":[{"award-number":["1813053"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2041920"],"award-info":[{"award-number":["2041920"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s10107-022-01799-3","type":"journal-article","created":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T16:42:59Z","timestamp":1648658579000},"page":"991-1007","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Robust k-center with two types of radii"],"prefix":"10.1007","volume":"197","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[]},{"given":"Maryam","family":"Negahbani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"issue":"2","key":"1799_CR1","first-page":"20","volume":"15","author":"D Adjiashvili","year":"2018","unstructured":"Adjiashvili, D., Baggio, A., Zenklusen, R.: Firefighting on trees beyond integrality gaps. ACM Trans. Algorithms (TALG) 15(2), 20 (2018)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"1","key":"1799_CR2","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/151002320","volume":"46","author":"H An","year":"2017","unstructured":"An, H., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. SIAM J. Comput. (SICOMP) 46(1), 272\u2013306 (2017)","journal-title":"SIAM J. Comput. (SICOMP)"},{"key":"1799_CR3","doi-asserted-by":"crossref","unstructured":"Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R.: A technique for obtaining true approximations for $$k$$-center with covering constraints. In: Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 52\u201365 (2020)","DOI":"10.1007\/978-3-030-45771-6_5"},{"key":"1799_CR4","doi-asserted-by":"crossref","unstructured":"Angelidakis, H., Makarychev, K., Makarychev, Y.: Algorithms for stable and perturbation-resilient problems. In: Proceedings, ACM Symposium on Theory of Computing (STOC), pp. 438\u2013451 (2017)","DOI":"10.1145\/3055399.3055487"},{"issue":"1\u20132","key":"1799_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2011.10.006","volume":"112","author":"P Awasthi","year":"2012","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Center-based clustering under perturbation stability. Inform. Process. Lett. 112(1\u20132), 49\u201354 (2012)","journal-title":"Inform. Process. Lett."},{"key":"1799_CR6","unstructured":"Bandyapadhyay, S.: On Perturbation resilience of non-uniform $$k$$-center. In: Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) (2020)"},{"key":"1799_CR7","unstructured":"Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.R.: A constant approximation for colorful k-center. In: Proceedings, European Symposium on Algorithms (ESA), pp. 12:1\u201312:14 (2019)"},{"key":"1799_CR8","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":"1799_CR9","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00453-013-9862-4","volume":"72","author":"D Chakrabarty","year":"2015","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of capacitated network design. Algorithmica 72(2), 493\u2013514 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"1799_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3392720","volume":"16","author":"D Chakrabarty","year":"2020","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform $$k$$-center problem. ACM Trans. Algorithms (TALG) 16(4), 1\u201319 (2020)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"1799_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3338513","volume":"15","author":"D Chakrabarty","year":"2019","unstructured":"Chakrabarty, D., Negahbani, M.: Generalized center problems with outliers. ACM Trans. Algorithms (TALG) 15(3), 1\u201314 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1799_CR12","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Resource minimization for fire containment. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1334\u20131349 (2010)","DOI":"10.1137\/1.9781611973075.108"},{"key":"1799_CR13","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 642\u2013651 (2001)"},{"key":"1799_CR14","unstructured":"Chekuri, C.S., Gupta, S.: Perturbation resilient clustering for $$k$$-center and related problems via LP relaxations. In: Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp.\u00a09 (2018)"},{"issue":"16","key":"1799_CR15","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.1016\/j.disc.2005.12.053","volume":"307","author":"S Finbow","year":"2007","unstructured":"Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discret. Math. 307(16), 2094\u20132105 (2007)","journal-title":"Discret. Math."},{"key":"1799_CR16","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"1799_CR17","doi-asserted-by":"publisher","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, 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1799_CR18","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533\u2013550 (1986)","journal-title":"J. ACM"},{"key":"1799_CR19","doi-asserted-by":"crossref","unstructured":"Jia, X., Rohwedder, L., Sheth, K., Svensson, O.: Towards non-uniform $$k$$-center with constant types of radii. In: Proceedings, ACM-SIAM Symposium on Simplicity in Algorithms (SOSA) (2022)","DOI":"10.1137\/1.9781611977066.16"},{"key":"1799_CR20","doi-asserted-by":"crossref","unstructured":"Jia, X., Sheth, K., Svensson, O.: Fair colorful $$k$$-center clustering. In: Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 209\u2013222 (2020)","DOI":"10.1007\/978-3-030-45771-6_17"},{"key":"1799_CR21","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2\u20137 (2011)","journal-title":"Optima"},{"key":"1799_CR22","doi-asserted-by":"crossref","unstructured":"Li, S.: On uniform capacitated $$k$$-median beyond the natural LP relaxation. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 696\u2013707 (2015)","DOI":"10.1137\/1.9781611973730.47"},{"key":"1799_CR23","doi-asserted-by":"crossref","unstructured":"Li, S.: Approximating capacitated $$k$$-median with (1 + $$\\varepsilon $$)k open facilities. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 786\u2013796 (2016)","DOI":"10.1137\/1.9781611974331.ch56"},{"key":"1799_CR24","unstructured":"Rahgoshay, M., Salavatipour, M.R.: Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment. In: Proceedings, International Symposium on Theoretical Aspects of Computer Science (STACS) (2020)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01799-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01799-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01799-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:19:32Z","timestamp":1675703972000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01799-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,30]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1799"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01799-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,30]]},"assertion":[{"value":"31 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}