hide
Free keywords:
-
Abstract:
The location of facilities in order to provide service for customers is a
well-studied problem in
the operations research literature. In the basic model, there is a predefined
cost for opening a facility
and also for connecting a customer to a facility, the goal being to minimize
the total cost. Often,
both in the case of public facilities (such as libraries, municipal swimming
pools, fire stations, ...)
and private facilities (such as distribution centers, switching stations, ...),
we may want to find a
‘fair’ allocation of the total cost to the customers—--this is known as the
cost allocation problem.
A central question in cooperative game theory is whether the total cost can be
allocated to the
customers such that no coalition of customers has any incentive to build their
own facility or to ask a
competitor to service them. We establish strong connections between fair cost
allocations and linear
programming relaxations for several variants of the facility location problem.
In particular, we show
that a fair cost allocation exists if and only if there is no integrality gap
for a corresponding linear
programming relaxation; this was only known for the simplest unconstrained
variant of the facility
location problem. Moreover, we introduce a subtle variant of randomized
rounding and derive new
proofs for the existence of fair cost allocations for several classes of
instances. We also show that it is
in general NP-complete to decide whether a fair cost allocation exists and
whether a given allocation
is fair.
