Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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