{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:36:58Z","timestamp":1787341018847,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,8,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider the classic Facility Location problem on planar graphs, in both the uniform and the nonuniform versions. Given an edge-weighted planar graph [Formula: see text], a set of clients [Formula: see text], a set of facilities [Formula: see text], and opening costs [Formula: see text], the goal of the nonuniform facility location is to find a subset [Formula: see text] of [Formula: see text] that minimizes [Formula: see text]. In the uniform case, [Formula: see text] is the same for all [Formula: see text]. The (nonuniform) Facility Location problem remains one of the most classic and fundamental optimization problem for which it was not known whether it admits a polynomial-time approximation scheme on planar graphs. We solve this open problem by giving an algorithm that, for any [Formula: see text], computes a solution of cost at most [Formula: see text] times the optimum in time [Formula: see text]. Moreover, for the [Formula: see text]-Median problem we propose an Efficient Bicriteria Approximation Scheme: for any [Formula: see text], in time [Formula: see text] we can compute a set of at most [Formula: see text] facilities whose opening yields connection cost at most [Formula: see text] times the optimum connection cost for opening at most [Formula: see text] facilities, with high probability. This immediately implies the first efficient approximation scheme for Uniform Facility Location.<\/jats:p>","DOI":"10.1137\/20m1350856","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T03:04:48Z","timestamp":1751857488000},"page":"FOCS19-420-FOCS19-471","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs"],"prefix":"10.1137","volume":"54","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, Laboratoire d\u2019informatique de Paris 6, LIP6, F-75252 Paris, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":true,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw 02-097, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw 02-097, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"ref2","unstructured":"V. Braverman, D. Feldman, and H. Lang, New Frameworks for Offline and Streaming Coreset Constructions, CoRR preprint, abs\/1612.00889, 2016."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/2981561"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9417-5"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.29"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.30"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, F. Grandoni, E. Lee, and C. Schwiegelshohn, Breaching the 2 LMP approximation barrier for facility location with applications to k-median, in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, N. Bansal and V. Nagarajan, eds. SIAM, 2023, pp. 940\u2013986, https:\/\/doi.org\/10.1137\/1.9781611977554.ch37.","DOI":"10.1137\/1.9781611977554.ch37"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, A. Gupta, L. Hu, H. Oh, and D. Saulpic, An improved local search algorithm for k-median, in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, J. S. Naor and N. Buchbinder, eds. SIAM, 2022, pp. 1556\u20131612, https:\/\/doi.org\/10.1137\/1.9781611977073.65.","DOI":"10.1137\/1.9781611977073.65"},{"key":"ref10","first-page":"42:1","volume-title":"ICALP 2019, LIPIcs 132","author":"Cohen-Addad V.","year":"2019"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/17M112717X"},{"key":"ref12","first-page":"33:1","volume-title":"ESA 2019, LIPIcs 1441","author":"Cohen-Addad V.","year":"2019"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00042"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.47"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"J. Erickson, K. Fox, and L. Lkhamsuren, Holiest minimum-cost paths and flows in surface graphs, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, 2018, I. Diakonikolas, D. Kempe, and M. Henzinger, eds. ACM, 2018, pp. 1319\u20131332.","DOI":"10.1145\/3188745.3188904"},{"key":"ref16","first-page":"569","volume-title":"STOC 2011","author":"Feldman D."},{"key":"ref17","first-page":"50","volume-title":"STOC 2003","author":"Fernandez de la Vega W.","year":"2003"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.66"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"K. N. Gowda, T. W. Pensyl, A. Srinivasan, and K. Trinh, Improved bi-point rounding algorithms and a golden barrier for k-median, in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, N. Bansal and V. Nagarajan, eds. SIAM, 2023, pp. 987\u20131011, https:\/\/doi.org\/10.1137\/1.9781611977554.ch38.","DOI":"10.1137\/1.9781611977554.ch38"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582157"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581035"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010019"},{"key":"ref30","series-title":"LIPIcs, 112","first-page":"65:1","volume-title":"ESA 2018","author":"Pilipczuk M.","year":"2018"},{"key":"ref31","first-page":"265","volume-title":"STOC 1997","author":"Shmoys D. B.","year":"1997"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1350856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:01:04Z","timestamp":1787338864000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1350856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1137\/20M1350856"],"URL":"https:\/\/doi.org\/10.1137\/20m1350856","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]}}}