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. We use this insight in order to give
proofs for the existence of fair cost allocations for several classes
of instances based on a subtle variant of randomized rounding. This
also leads to polynomial-time algorithms to solve the facility
location problem in these cases. We also prove that it is in general
NP-complete to decide whether a fair cost allocation exists and
whether a given allocation is fair.
