Facility Location with Nonuniform Hard
Capacities

Martin Pal

Abstract:

In this paper we give the first constant factor approximation
algorithm for the Facility Location Problem with nonuniform, hard
capacities. Facility location problems received a great deal of
attention in recent years. Approximation algorithms have been
developed for many variants. Most of these algorithms are based
on linear programming, but the linear programming techniques developed
thus far have been unsuccessful in dealing with hard capacities.

A local-search based approximation algorithm by Korupolu et al
and Chudak and Williamson \cite{KoPlRa98b,ChuWil99} is known for
the special case of hard but uniform capacities. We present a
local-search heuristic that yields an approximation guarantee
of $9+\epsilon$ for the case of nonuniform hard capacities. To
obtain this result we introduce new operations that are natural
in this context. Our proof is based on network flow techniques.

(Joint work with Eva Tardos and
Tom Wexler)