A Concentration Inequality for the Facility Location Problem

DOI10.1016/J.ORL.2022.01.009zbMATH Open1525.90259arXiv2012.04488MaRDI QIDQ6355581

Publication date: 8 December 2020

Abstract: We give a concentration inequality for a stochastic version of the facility location problem. We show the objective

C_{n} = m i n_{F s u b s e t e q [0, 1]^{2}} | F | + s u m_{x i n X} m i n_{f i n F} | x - f |

is concentrated in an interval of length

O (n^{1 / 6})

and

E [C_{n}] = T h e t a (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.

Mathematics Subject Classification ID

Stochastic programming (90C15) Discrete location and assignment (90B80)

This page was built for publication: A Concentration Inequality for the Facility Location Problem