Fast Approximation Algorithms for Geometric Uniform Facility Location

We consider the Euclidean facility location problem with uniform opening costs and present for a very simple and fast polynomial-time approximation scheme (PTAS), running in time O(n log^2n loglog n). The novel ingredient of our algorithms is a simple decomposition scheme that enables to partition the input points into disjoint point sets that can then be considered independently.

We also briefly mention the application of this result to design the first (1+epsilon)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams using polylogarithmic space.

Joint work with C. Lammersen (SAP), M. Monemizadeh (Frankfurt), and C. Sohler (TU Dortmund).