Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor(s)
Author(s):
Epstein, Leah
van Stee, Rob		dblp
dblp
Not MPG Author(s):
Epstein, Leah

BibTeX cite key*:

vanStee2009a

Title

Title*:

On the online unit clustering problem

Journal

Journal Title*:

ACM Transactions on Algorithms
Journal's URL:

http://portal.acm.org/browse_dl.cfm?linked=1&part=transaction&idx=J982&coll=portal&dl=ACM

Download URL
for the article:

http://doi.acm.org/10.1145/1868237.1868245
Language:

English

Publisher

Publisher's
Name:

ACM
Publisher's URL:


Publisher's
Address:

New York, NY
ISSN:

1549-6325

Vol, No, pp, Date

Volume*:

7
Number:

1

Publishing Date:

2010

Pages*:

1-18
Number of
VG Pages:


Page Start:

7:1
Page End:

7:18

Sequence Number:

7
DOI:

10.1145/1868237.1868245

Note, Abstract, ©

Note:


(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.

URL for the Abstract:


Categories,
Keywords:

online algorithms, clustering

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

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


BibTeX Entry:

@ARTICLE{vanStee2009a,
AUTHOR = {Epstein, Leah and van Stee, Rob},
 TITLE = {On the online unit clustering problem},
 JOURNAL = {ACM Transactions on Algorithms},
 PUBLISHER = {ACM},
 YEAR = {2010},
 NUMBER = {1},
 VOLUME = {7},
 PAGES = {1--18},
 ADDRESS = {New York, NY},
 ISBN = {1549-6325},
 DOI = {10.1145/1868237.1868245},
}

Entry last modified by Manuel Lamotte-Schubert, 03/28/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
[Library]		Created
02/13/2009 12:24:01 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Manuel Lamotte-Schubert
Christina Fries
Christina Fries
Anja Becker
Anja Becker		Edit Dates
28.03.2011 10:58:04
25.01.2011 14:44:18
25.01.2011 14:42:05
04.01.2011 13:54:10
02-12-2010 15:54:28