English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Incremental Algorithms for Facility Location and k-Median

Fotakis, D. (2004). Incremental Algorithms for Facility Location and k-Median. In Algorithms – ESA 2004: 12th Annual European Symposium (pp. 347-358). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2932-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2934-E
Genre: Conference Paper

Files

show Files
hide Files
:
fotakis.pdf (Any fulltext), 203KB
 
File Permalink:
-
Name:
fotakis.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           
Albers, Susanne1, Editor           
Radzik, Tomasz2, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Max Planck Society, ou_persistent13              

Content

show
hide
Free keywords: -
 Abstract: In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing cluster or placing it in a new singleton cluster. The algorithm can also merge some of the existing clusters at any point in time. We present the first incremental algorithm for Facility Location with uniform facility costs which achieves a constant performance ratio and the first incremental algorithm for k-Median which achieves a constant performance ratio using O(k) medians.

Details

show
hide
Language(s): eng - English
 Dates: 2005-04-222004
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 231194
Other: Local-ID: C1256428004B93B8-BB4F865FF034AAE3C1256FB4004B625B-Fotakis2004a
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Bergen, Norway
Start-/End Date: 2004-09-14

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms – ESA 2004: 12th Annual European Symposium
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 347 - 358 Identifier: ISBN: 3-540-23025-4

Source 2

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