A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs

Abstract

We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph $G$, a set of clients $C\subseteq V(G)$, a set of facilities $F\subseteq V(G)$, and opening costs $\mathsf{open}:F\to {\mathbb{R}}_{\ge 0}$, the goal is to find a subset $D$ of $F$ that minimizes ${\sum }_{c\in C}{\min }_{f\in D}\mathrm{dist}(c,f)+{\sum }_{f\in D}\mathsf{open}(f)$. The Facility Location problem remains one of the most classic and fundamental optimization problem for which it is not known whether it admits a polynomial-time approximation scheme (PTAS) on planar graphs despite significant effort for obtaining one. We solve this open problem by giving an algorithm that for any $\epsilon >0$, computes a solution of cost at most $(1+\epsilon )$ times the optimum in time $n^{2^{O({\epsilon }^{-2}\log (1/\epsilon ))}}$.

37 pages