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:








Author, Editor

Author(s):

Fotakis, Dimitris

dblp



Editor(s):

Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.

BibTeX cite key*:

Fot03

Title, Booktitle

Title*:

On the Competitive Ratio for Online Facility Location


icalp03.pdf (229.42 KB)

Booktitle*:

Automata, languages and programming : 30th International Colloquium, ICALP 2003

Event, URLs

URL of the conference:

http://www.win.tue.nl/icalp2003/

URL for downloading the paper:

http://link.springer.de/link/service/series/0558/papers/2719/27190637.pdf

Event Address*:

Eindhoven, The Netherlands

Language:

English

Event Date*
(no longer used):

June, 30 - July, 4

Organization:

European Association of Theoretical Computer Science (EATCS)

Event Start Date:

30 June 2003

Event End Date:

4 July 2003

Publisher

Name*:

Springer

URL:

http://www.springer.de/

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

2719

Number:


Month:

June

Pages:

637-652

Year*:

2003

VG Wort Pages:


ISBN/ISSN:

3-540-40493-7

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We consider the problem of Online Facility Location, where demands arrive online and must be irrevocably assigned to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We prove that the competitive ratio for Online Facility Location is $\Theta(\frac{\log n}{\log\log n})$. On the negative side, we show that no randomized algorithm can achieve a competitive ratio better than $O(\frac{\log n}{\log\log n})$ against an oblivious adversary even if the demands lie on a line segment. On the positive side, we present a deterministic algorithm achieving a competitive ratio of $O(\frac{\log n}{\log\log n})$. The analysis is based on a hierarchical decomposition of the optimal facility locations such that each component either is relatively well-separated or has a relatively large diameter, and a potential function argument which distinguishes between the two kinds of components.

Keywords:

Online Algorithms



Download
Access Level:

Public

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{Fot03,
AUTHOR = {Fotakis, Dimitris},
EDITOR = {Baeten, Jos C.M. and Lenstra, Jan Karel and Parrow, Joachim and Woeginger, Gerhard J.},
TITLE = {On the Competitive Ratio for Online Facility Location},
BOOKTITLE = {Automata, languages and programming : 30th International Colloquium, ICALP 2003},
PUBLISHER = {Springer},
YEAR = {2003},
ORGANIZATION = {European Association of Theoretical Computer Science (EATCS)},
VOLUME = {2719},
PAGES = {637--652},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Eindhoven, The Netherlands},
MONTH = {June},
ISBN = {3-540-40493-7},
}


Entry last modified by Christine Kiesel, 03/02/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)
Dimitris Fotakis
Created
04/09/2003 02:16:46 PM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
15.06.2004 14:33:07
15.06.2004 14:31:03
11.06.2004 17:06:33
11.06.2004 17:06:21
06/24/2003 01:55:19 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
icalp03.pdf