MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Epstein, Leah
van Stee, Rob
dblp
dblp
Not MPG Author(s):
Epstein, Leah
Editor(s):
Kaklamanis, Christos
Skutella, Martin
dblp
dblp
Not MPII Editor(s):
Kaklamanis, Christos
Skutella, Martin
BibTeX cite key*:
vanStee2008k
Title, Booktitle
Title*:
On the Online Unit Clustering Problem
unitj3.dvi (76.8 KB)
Booktitle*:
Approximation and Online Algorithms, 5th International Workshop, WAOA 2007
Event, URLs
Conference URL::
http://www.algo07.cs.tau.ac.il/waoa.html
Downloading URL:
http://www.springerlink.com/content/221m1721nv567730/fulltext.pdf
Event Address*:
Eilat, Israel
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
11 October 2007
Event End Date:
12 October 2007
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4927
Number:
Month:
February
Pages:
193-206
Year*:
2008
VG Wort Pages:
14
ISBN/ISSN:
0302-9743
Sequence Number:
DOI:
10.1007/978-3-540-77918-6_16
Note, Abstract, ©
(LaTeX) Abstract:
We continue the study of the online unit clustering problem,
introduced by Chan and Zarrabi-Zadeh (\emph{Workshop on Approximation and
Online Algorithms 2006}, LNCS 4368, p.121--131. Springer, 2006).
We design a deterministic
algorithm with a competitive ratio of $7/4$ for the
one-dimensional case. This is the first deterministic algorithm
that beats the bound of 2. It also has a better competitive ratio
than the previous randomized algorithms. Moreover, we provide the
first non-trivial deterministic lower bound, improve the
randomized lower bound, and prove the first lower bounds for
higher dimensions.
Keywords:
online algorithms, clustering
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{vanStee2008k,
AUTHOR = {Epstein, Leah and van Stee, Rob},
EDITOR = {Kaklamanis, Christos and Skutella, Martin},
TITLE = {On the Online Unit Clustering Problem},
BOOKTITLE = {Approximation and Online Algorithms, 5th International Workshop, WAOA 2007},
PUBLISHER = {Springer},
YEAR = {2008},
VOLUME = {4927},
PAGES = {193--206},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Eilat, Israel},
MONTH = {February},
ISBN = {0302-9743},
DOI = {10.1007/978-3-540-77918-6_16},
}


Entry last modified by Rob van Stee, 12/10/2010
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)
Rob van Stee
Created
01/12/2009 01:44:41 PM
Revisions
2.
1.
0.

Editor(s)
Rob van Stee
Rob van Stee
Rob van Stee

Edit Dates
12-10-2010 15:34:28
02/19/2009 01:29:44 PM
01/12/2009 01:44:42 PM


File Attachment Icon
unitj3.dvi