文章基本信息

标题：Cooperative facility location games
本地全文：下载
作者：Michel X. GOEMANS ; Martin SKUTELLA
期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2000
卷号：2000
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：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 predeﬁned cost for opening a facility and also for con- necting 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, ﬁre stations, ...) and private facilities (such as distribu- tion centers, switching stations, ...), we may want to ﬁnd 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 cus- tomers 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 lin- ear 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 NP- complete to decide whether a fair cost allocation exists and whether a given allocation is fair.
关键词：facility location, cooperative games, LP relaxation, random- ized rounding, core