{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T15:50:59Z","timestamp":1756309859957,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T00:00:00Z","timestamp":1671494400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T00:00:00Z","timestamp":1671494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2019R1C1C1008934","NRF-2016R1C1B1012910"],"award-info":[{"award-number":["NRF-2019R1C1C1008934","NRF-2016R1C1B1012910"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002573","name":"Yonsei University","doi-asserted-by":"publisher","award":["2018-22-0093"],"award-info":[{"award-number":["2018-22-0093"]}],"id":[{"id":"10.13039\/501100002573","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Institute of Information & Communications Technology Planning & Evaluation","award":["2021-0-02068","2022-22-0002"],"award-info":[{"award-number":["2021-0-02068","2022-22-0002"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,7]]},"DOI":"10.1007\/s00453-022-01060-5","type":"journal-article","created":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T12:03:39Z","timestamp":1671537819000},"page":"1883-1911","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location and k-Center"],"prefix":"10.1007","volume":"85","author":[{"given":"Kangsan","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongho","family":"Shin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3690-4621","authenticated-orcid":false,"given":"Hyung-Chan","family":"An","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,20]]},"reference":[{"key":"1060_CR1","unstructured":"Adamaszek, A., Antoniadis, A., Kumar, A., M\u00f6mke, T.: Approximating airports and railways. In: Symposium on Theoretical Aspects of Computer Science (STACS), vol. 6, pp 5:1\u20135:13 2018"},{"issue":"4","key":"1060_CR2","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1109\/32.16608","volume":"15","author":"M Ahamad","year":"1989","unstructured":"Ahamad, M., Ammar, M.H.: Performance characterization of quorum-consensus algorithms for replicated data. IEEE Trans. Softw. Eng. 15(4), 492\u2013496 (1989)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"1060_CR3","doi-asserted-by":"crossref","unstructured":"Ahmadian, S., Friggstad, Z., Swamy, C.: Local-search based approximation algorithms for mobile facility location problems. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1607\u20131621 2013","DOI":"10.1137\/1.9781611973105.115"},{"issue":"1","key":"1060_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10107-014-0857-y","volume":"154","author":"HC An","year":"2015","unstructured":"An, H.C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated $$k$$-center. Math. Program. 154(1), 29\u201353 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"1060_CR5","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/151002320","volume":"46","author":"HC An","year":"2017","unstructured":"An, H.C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. SIAM J. Comput. 46(1), 272\u2013306 (2017)","journal-title":"SIAM J. Comput."},{"key":"1060_CR6","volume-title":"On finding integer solutions to linear programs","author":"ML Balinski","year":"1964","unstructured":"Balinski, M.L.: On finding integer solutions to linear programs. Tech. Rep. Mathematica Princeton, NJ (1964)"},{"key":"1060_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: European Symposium on Algorithms (ESA), pp 133\u2013144 2012","DOI":"10.1007\/978-3-642-33090-2_13"},{"key":"1060_CR8","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., F\u00fcl\u00f6p, O.: Fast algorithms for even\/odd minimum cuts and generalizations. In: European Symposium on Algorithms (ESA), pp 88\u201399 2000","DOI":"10.1007\/3-540-45253-2_9"},{"key":"1060_CR9","doi-asserted-by":"crossref","unstructured":"Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp 29\u201343 2007","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"1060_CR10","unstructured":"Byrka, J., Ghodsi, M., Srinivasan, A.: LP-rounding algorithms for facility-location problems. arXiv preprint arXiv:1007.3611 2010"},{"key":"1060_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.H.H., Guerqin, A., Sozio, M.: Fully dynamic $$k$$-center clustering. In: World Wide Web Conference (WWW), pp 579\u2013587 2018","DOI":"10.1145\/3178876.3186124"},{"issue":"1","key":"1060_CR12","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/s00453-013-9850-8","volume":"72","author":"J Cheriyan","year":"2015","unstructured":"Cheriyan, J., Friggstad, Z., Gao, Z.: Approximating minimum-cost connected $$T$$-joins. Algorithmica 72(1), 126\u2013147 (2015)","journal-title":"Algorithmica"},{"key":"1060_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for $$k$$-centers with non-uniform hard capacities. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp 273\u2013282 2012","DOI":"10.1109\/FOCS.2012.63"},{"key":"1060_CR14","unstructured":"Cygan, M., Czumaj, A., Mucha, M., Sankowski, P.: Online facility location with deletions. In: European Symposium on Algorithms (ESA), pp 21:1\u201321:15 2018"},{"issue":"1","key":"1060_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for $$(k, r)$$-center in planar graphs and map graphs. ACM Trans. Algorithm. 1(1), 33\u201347 (2005)","journal-title":"ACM Trans. Algorithm."},{"key":"1060_CR16","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"1060_CR17","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P.N., Mathieu, C.: Approximating k-center in planar graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 617\u2013627 2014a","DOI":"10.1137\/1.9781611973402.47"},{"key":"1060_CR18","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Mathieu, C., Schabanel, N.: Facility location in evolving metrics. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp 459\u2013470 2014b","DOI":"10.1007\/978-3-662-43951-7_39"},{"key":"1060_CR19","unstructured":"Ene, A., Har-Peled, S., Raichel, B.: Fast clustering with lower bounds: No customer too far, no shop too small. arXiv preprint arXiv:1304.7318 2013"},{"key":"1060_CR20","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0012-365X(96)00174-4","volume":"165","author":"H Everett","year":"1997","unstructured":"Everett, H., de Figueiredo, C.M., Linhares-Sales, C., Maffray, F., Porto, O., Reed, B.A.: Path parity and perfection. Discret. Math. 165, 233\u2013252 (1997)","journal-title":"Discret. Math."},{"key":"1060_CR21","unstructured":"Goranci, G., Henzinger, M., Leniowski, D.: A tree structure for dynamic facility location. In: European Symposium on Algorithms (ESA), pp 39:1\u201339:13 2018"},{"issue":"1","key":"1060_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0167-6377(81)90020-1","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Pulleyblank, W.R.: Weakly bipartite graphs and the max-cut problem. Oper. Res. Lett. 1(1), 23\u201327 (1981)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1060_CR23","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"4","key":"1060_CR24","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02579139","volume":"4","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Corrigendum to our paper \u201cthe ellipsoid method and its consequences in combinatorial optimization\u2019\u2019. Combinatorica 4(4), 291\u2013295 (1984)","journal-title":"Combinatorica"},{"issue":"2","key":"1060_CR25","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(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1060_CR26","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and $$k$$-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"1060_CR27","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: ACM Symposium on Theory of Computing (STOC), pp 731\u2013740 2002","DOI":"10.1145\/509907.510012"},{"key":"1060_CR28","doi-asserted-by":"crossref","unstructured":"Kakimura, N., Kawarabayashi, K., Kobayashi, Y. Erd\u0151s-P\u00f3sa property and its algorithmic applications \u2014 parity constraints, subset feedback set, and subset packing. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1726\u20131736 2012","DOI":"10.1137\/1.9781611973099.137"},{"key":"1060_CR29","doi-asserted-by":"crossref","unstructured":"Kaminski, M., Nishimura, N.: Finding an induced path of given parity in planar graphs in polynomial time. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 656\u2013670 2012","DOI":"10.1137\/1.9781611973099.55"},{"issue":"3","key":"1060_CR30","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Sussmann, Y.: The capacitated $$k$$-center problem. SIAM J. Discret. Math. 13(3), 403\u2013418 (2000)","journal-title":"SIAM J. Discret. Math."},{"key":"1060_CR31","unstructured":"Kim, K., Shin, Y., An, H.C.: Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem. In: International Symposium on Algorithms and Computation (ISAAC), Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp 21:1\u201321:17 2020"},{"issue":"1","key":"1060_CR32","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"MR Korupolu","year":"2000","unstructured":"Korupolu, M.R., Plaxton, C., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithm. 37(1), 146\u2013188 (2000)","journal-title":"J. Algorithm."},{"issue":"4","key":"1060_CR33","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"AA Kuehn","year":"1963","unstructured":"Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manage. Sci. 9(4), 643\u2013666 (1963)","journal-title":"Manage. Sci."},{"key":"1060_CR34","doi-asserted-by":"crossref","unstructured":"Lammersen, C., Sohler, C.: Facility location in dynamic geometric data streams. In: European Symposium on Algorithms (ESA), pp 660\u2013671 2008","DOI":"10.1007\/978-3-540-87744-8_55"},{"key":"1060_CR35","doi-asserted-by":"crossref","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp 77\u201388 2011","DOI":"10.1007\/978-3-642-22012-8_5"},{"key":"1060_CR36","doi-asserted-by":"crossref","unstructured":"Li, S.: On facility location with general lower bounds. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 2279\u20132290 2019","DOI":"10.1137\/1.9781611975482.138"},{"issue":"2","key":"1060_CR37","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","volume":"11","author":"AS Manne","year":"1964","unstructured":"Manne, A.S.: Plant location under economies-of-scale\u2013decentralization and computation. Manage. Sci. 11(2), 213\u2013235 (1964)","journal-title":"Manage. Sci."},{"key":"1060_CR38","doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: European Symposium on Algorithms (ESA), pp 865\u2013877 2015","DOI":"10.1007\/978-3-662-48350-3_72"},{"issue":"4","key":"1060_CR39","doi-asserted-by":"publisher","first-page":"50:1","DOI":"10.1145\/1383369.1383381","volume":"4","author":"J Ma\u00dfberg","year":"2008","unstructured":"Ma\u00dfberg, J., Vygen, J.: Approximation algorithms for a facility location problem with service capacities. ACM Trans. Algorithm. 4(4), 50:1-50:15 (2008)","journal-title":"ACM Trans. Algorithm."},{"key":"1060_CR40","doi-asserted-by":"crossref","unstructured":"Matuschke, J., Bley, A., M\u00fcller, B.: Approximation algorithms for facility location with capacitated and length-bounded tree connections. In: European Symposium on Algorithms (ESA), pp 707\u2013718 2013","DOI":"10.1007\/978-3-642-40450-4_60"},{"issue":"1","key":"1060_CR41","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"MW Padberg","year":"1982","unstructured":"Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and $$b$$-matchings. Math. Oper. Res. 7(1), 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"1060_CR42","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T.: Facility location with nonuniform hard capacities. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp 329\u2013338 2001","DOI":"10.1109\/SFCS.2001.959907"},{"key":"1060_CR43","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Springer, Berlin (2003)"},{"key":"1060_CR44","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jctb.1994.1070","volume":"62","author":"A Schrijver","year":"1994","unstructured":"Schrijver, A., Seymour, P.: Packing odd paths. J. Comb. Theory 62, 280\u2013288 (1994)","journal-title":"J. Comb. Theory"},{"key":"1060_CR45","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A.: Eight-fifth approximation for the path TSP. In: Integer Programming and Combinatorial Optimization (IPCO), pp 362\u2013374 2013","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"1060_CR46","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems. In: ACM Symposium on Theory of Computing (STOC), pp 265\u2013274 1997","DOI":"10.1145\/258533.258600"},{"issue":"3","key":"1060_CR47","doi-asserted-by":"publisher","first-page":"631","DOI":"10.2307\/1235442","volume":"45","author":"JF Stollsteimer","year":"1963","unstructured":"Stollsteimer, J.F.: A working model for plant numbers and locations. J. Farm Econ. 45(3), 631\u2013645 (1963)","journal-title":"J. Farm Econ."},{"key":"1060_CR48","unstructured":"The Apache Software Foundation: Apache ZooKeeper. http:\/\/zookeeper.apache.org\/ 2020"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01060-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01060-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01060-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T05:57:26Z","timestamp":1687499846000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01060-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,20]]},"references-count":48,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1060"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01060-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,12,20]]},"assertion":[{"value":"16 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 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"}}]}}