论文标题
设施位置问题的集中不平等
A Concentration Inequality for the Facility Location Problem
论文作者
论文摘要
我们为设施位置问题的随机版本提供集中不平等。我们显示目标$ c_n = \ min_ {f \ subseteq [0,1]^2} | f |++\ sum_ {x \ in x} \ min_ {f} \ in f} \ | x-f \ | $集中在长度$ o（n^{1/6}} $和$ \ \ \ \ \ \ e [c_-n^{1/6} $和3}的间隔中如果输入$ x $由I.I.D.组成单位正方形中的均匀点。我们的主要工具是使用以前用于设施位置问题的近似算法设计的几何数量，以分析Martingale过程。我们的许多技术都将其推广到其他设置。
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}\|x-f\|$ 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.
