Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://algo2009.itu.dk/7th-waoa

URL for downloading the paper:


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
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)
[Library]
Created
12/09/2010 03:41:48 PM
Revision
1.
0.


Editor
Anja Becker
Rob van Stee


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