Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2013) | last year (2012) | two years ago (2011) | 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)