A Concentration Inequality for the Facility Location Problem

Abstract

We give a concentration inequality for a stochastic version of the facility location problem. We show the objective $C_n={\min }_{F\subseteq [0,1{]}^2}|F|+{\sum }_{x\in X}{\min }_{f\in F}\Vert x-f\Vert$ is concentrated in an interval of length $O(n^{1/6})$ and $\E[C_n]=Θ(n^{2/3})$ if the input $X$ consists of i.i.d. uniform points in the unit square. Our main tool is to use a geometric quantity, previously used in the design of approximation algorithms for the facility location problem, to analyze a martingale process. Many of our techniques generalize to other settings.

Operations Research Letters, Volume 50