Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.algo07.cs.tau.ac.il/waoa.html

URL for downloading the paper:

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
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)
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
unitj3.dvi