MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Christodoulou, George
Chung, Christine
Ligett, Katrina
Pyrga, Evangelia
van Stee, Rob		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Chung, Christine
Ligett, Katrina
Editor(s):
Bampis, Evripidis
Jansen, Klaus		dblp
dblp
Not MPII Editor(s):
Bampis, Evripidis
Jansen, Klaus
BibTeX cite key*:
CCLPS2009
Title, Booktitle
Title*:
On the price of stability for undirected network design
Booktitle*:
Approximation and Online Algorithms : 7th International Workshop, WAOA 2009
Event, URLs
Conference URL::
http://algo2009.itu.dk/7th-waoa
Downloading URL:
Event Address*:
Copenhagen, Denmark
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 September 2009
Event End Date:
11 September 2009
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
5893
Number:
Month:
June
Pages:
86-97
Year*:
2010
VG Wort Pages:
12
ISBN/ISSN:
9-783642-12449-5
Sequence Number:
DOI:
10.1007/978-3-642-12450-1_8
Note, Abstract, ©
(LaTeX) Abstract:
We continue the study of the effects of selfish behavior in the
network design problem.
We provide new bounds for the price of stability for network design with
fair cost allocation for undirected graphs. We consider the most general
case, for which the best known upper bound is the Harmonic number
$H_n$, where $n$ is the number of agents,
and the best previously known lower bound is $12/7\approx1.778$.

We present a nontrivial lower bound of $42/23\approx1.8261$.
Furthermore,
we show that for two players, the price of stability is exactly $4/3$, while for
three players it is at least $74/48\approx 1.542$ and at most $1.65$.
These are the first improvements on the bound of $H_n$ for general networks.
In particular, this demonstrates a separation between the price of
stability on undirected graphs and that on directed graphs,
Previously, such a gap was only known for the cases where all players
have a shared source, and for weighted players.
Keywords:
price of stability, algorithmic game theory
Download
Access Level:
Priviledged Users

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{CCLPS2009,
AUTHOR = {Christodoulou, George and Chung, Christine and Ligett, Katrina and Pyrga, Evangelia and van Stee, Rob},
 EDITOR = {Bampis, Evripidis and Jansen, Klaus},
 TITLE = {On the price of stability for undirected network design},
 BOOKTITLE = {Approximation and Online Algorithms : 7th International Workshop, WAOA 2009},
 PUBLISHER = {Springer},
 YEAR = {2010},
 VOLUME = {5893},
 PAGES = {86--97},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Copenhagen, Denmark},
 MONTH = {June},
 ISBN = {9-783642-12449-5},
 DOI = {10.1007/978-3-642-12450-1_8},
}

Entry last modified by Anja Becker, 12/17/2010
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)
[Library]		Created
12/09/2010 15:41:48
Revision
1.
0.


Editor
Anja Becker
Rob van Stee


Edit Date
17.12.2010 13:44:24
12-09-2010 15:41:48