hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,
Abstract:
The $k$-Facility Location problem is a generalization of the classical
problems $k$-Median and Facility Location. The goal is to select a subset of at
most $k$ facilities that minimizes the total cost of opened facilities and
established connections between clients and opened facilities. We consider the
hard-capacitated version of the problem, where a single facility may only serve
a limited number of clients and creating multiple copies of a facility is not
allowed. We construct approximation algorithms slightly violating the
capacities based on rounding a fractional solution to the standard LP.
It is well known that the standard LP (even in the case of uniform capacities
and opening costs) has unbounded integrality gap if we only allow violating
capacities by a factor smaller than $2$, or if we only allow violating the
number of facilities by a factor smaller than $2$. In this paper, we present
the first constant-factor approximation algorithms for the hard-capacitated
variants of the problem. For uniform capacities, we obtain a
$(2+\varepsilon)$-capacity violating algorithm with approximation ratio
$O(1/\varepsilon^2)$; our result has not yet been improved. Then, for
non-uniform capacities, we consider the case of $k$-Median, which is equivalent
to $k$-Facility Location with uniform opening cost of the facilities. Here, we
obtain a $(3+\varepsilon)$-capacity violating algorithm with approximation
ratio $O(1/\varepsilon)$.
