Cooperative facility location games

Michel X. Goemans and Martin Skutella

No 2000014, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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. 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. We also prove that it is in general NPcomplete to decide whether a fair cost allocation exists and whether a given allocation is fair.

Keywords: facility location; cooperative games; LP relaxation; randomized rounding; core. (search for similar items in EconPapers)
Date: 2000-03
References: View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2000.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2000014

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().