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

Speaker(s)

Marcin Pilipczuk

Affiliation

University of Warsaw

Date

Nov. 7, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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 $w \colon F \to \mathbb{R}_{\geq 0}$, the goal is to find a subset $A$ of $F$ that minimizes $\sum_{c \in C} \min_{f \in A} \dist(c,f) + \sum_{f \in A} w(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 $\eps>0$, computes a solution of cost at most $(1+\eps)$ times the optimum in time $n^{2^{O(\eps^{-2} \log (1/\eps))}}$. Join work with Vincent Cohen-Addad and Michał Pilipczuk.

---