English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DA1-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DA4-5
Genre: Conference Paper

Files

show Files
hide Files
:
icalp03.pdf (Any fulltext), 230KB
 
File Permalink:
-
Name:
icalp03.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Fotakis, Dimitris1, Author           
Baeten, Jos C.M., Editor
Lenstra, Jan Karel, Editor
Parrow, Joachim, Editor
Woeginger, Gerhard J., Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2004-06-152003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 201835
Other: Local-ID: C1256428004B93B8-6A9C56FA859349F5C1256D030043742D-Fot03
 Degree: -

Event

show
hide
Title: ICALP 2003
Place of Event: Eindhoven, The Netherlands
Start-/End Date: 2003-06-30 - 2003-07-04

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, languages and programming : 30th International Colloquium, ICALP 2003
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 637 - 652 Identifier: ISBN: 3-540-40493-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2719 Sequence Number: - Start / End Page: - Identifier: -