An improved algorithm for online unit clustering

Hamid Zarrabi-Zadeh; Timothy M. Chan

doi:10.1007/s00453-008-9208-9

An improved algorithm for online unit clustering

Research output: Contribution to journal › Article › peer-review

Abstract

We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.

Original language	English (US)
Pages (from-to)	490-500
Number of pages	11
Journal	Algorithmica (New York)
Volume	54
Issue number	4
DOIs	https://doi.org/10.1007/s00453-008-9208-9
State	Published - Aug 2009
Externally published	Yes

Keywords

Online algorithms
Randomized algorithms
Unit clustering

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Online availability

10.1007/s00453-008-9208-9

Library availability

Discover UIUC Full Text

Cite this

@article{c145ba21caad4d118802e68a885adac9,

title = "An improved algorithm for online unit clustering",

abstract = "We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.",

keywords = "Online algorithms, Randomized algorithms, Unit clustering",

author = "Hamid Zarrabi-Zadeh and Chan, {Timothy M.}",

year = "2009",

month = aug,

doi = "10.1007/s00453-008-9208-9",

language = "English (US)",

volume = "54",

pages = "490--500",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - An improved algorithm for online unit clustering

AU - Zarrabi-Zadeh, Hamid

AU - Chan, Timothy M.

PY - 2009/8

Y1 - 2009/8

N2 - We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.

AB - We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.

KW - Online algorithms

KW - Randomized algorithms

KW - Unit clustering

UR - http://www.scopus.com/inward/record.url?scp=67349178110&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349178110&partnerID=8YFLogxK

U2 - 10.1007/s00453-008-9208-9

DO - 10.1007/s00453-008-9208-9

M3 - Article

AN - SCOPUS:67349178110

SN - 0178-4617

VL - 54

SP - 490

EP - 500

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 4

ER -

An improved algorithm for online unit clustering

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this