Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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