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: Goto entry point

 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:

 (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},