Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Goemans, Michel X.
Skutella, Martin

dblp
dblp

Not MPG Author(s):

Goemans, Michel X.

BibTeX cite key*:

GoemansSkutella2004

Title

Title*:

Cooperative facility location games

Journal

Journal Title*:

Journal of Algorithms

Journal's URL:

http://www.sciencedirect.com/science/journal/01966774

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0196-6774

Vol, No, pp, Date

Volume*:

50

Number:

2

Publishing Date:

February 2004

Pages*:

194-214

Number of
VG Pages:

30

Page Start:

194

Page End:

214

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

Facility location, Cooperative games, LP relaxation, Randomized rounding, Core

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

MPG Subsubunit:

Combinatorial Optimization Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{GoemansSkutella2004,
AUTHOR = {Goemans, Michel X. and Skutella, Martin},
TITLE = {Cooperative facility location games},
JOURNAL = {Journal of Algorithms},
PUBLISHER = {Elsevier},
YEAR = {2004},
NUMBER = {2},
VOLUME = {50},
PAGES = {194--214},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {February},
ISBN = {0196-6774},
}


Entry last modified by Uwe Brahm, 07/01/2005
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Martin Skutella
Created
02/02/2004 04:05:35 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Christine Kiesel
Christine Kiesel
Martin Skutella
Martin Skutella
Edit Dates
07/01/2005 05:22:12 PM
30.05.2005 15:54:11
30.05.2005 15:39:50
04.05.2004 16:13:28
02.02.2004 16:05:35