Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  On the Competitive Ratio for Online Facility Location

Fotakis, D. (2003). On the Competitive Ratio for Online Facility Location. In Automata, languages and programming: 30th International Colloquium, ICALP 2003 (pp. 637-652). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DA1-B Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DA4-5
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
icalp03.pdf (beliebiger Volltext), 230KB
 
Datei-Permalink:
-
Name:
icalp03.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Fotakis, Dimitris1, Autor           
Baeten, Jos C.M., Herausgeber
Lenstra, Jan Karel, Herausgeber
Parrow, Joachim, Herausgeber
Woeginger, Gerhard J., Herausgeber
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2004-06-152003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 201835
Anderer: Local-ID: C1256428004B93B8-6A9C56FA859349F5C1256D030043742D-Fot03
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: ICALP 2003
Veranstaltungsort: Eindhoven, The Netherlands
Start-/Enddatum: 2003-06-30 - 2003-07-04

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Automata, languages and programming : 30th International Colloquium, ICALP 2003
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 637 - 652 Identifikator: ISBN: 3-540-40493-7

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 2719 Artikelnummer: - Start- / Endseite: - Identifikator: -