A randomized algorithm for online unit clustering

Timothy M. Chan; Hamid Zarrabi-Zadeh

doi:10.1007/s00224-007-9085-7

A randomized algorithm for online unit clustering

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

Abstract

In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.

Original language	English (US)
Pages (from-to)	486-496
Number of pages	11
Journal	Theory of Computing Systems
Volume	45
Issue number	3
DOIs	https://doi.org/10.1007/s00224-007-9085-7
State	Published - Jul 2009
Externally published	Yes

Keywords

Online algorithms
Randomized algorithms
Unit clustering

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Online availability

10.1007/s00224-007-9085-7

Library availability

Discover UIUC Full Text

Cite this

@article{0ad5c724b1d54b9d8cf5bab1028fa813,

title = "A randomized algorithm for online unit clustering",

abstract = "In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the na{\"i}ve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.",

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

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

note = "Funding Information: Work of the first author has been supported in part by NSERC.",

year = "2009",

month = jul,

doi = "10.1007/s00224-007-9085-7",

language = "English (US)",

volume = "45",

pages = "486--496",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - A randomized algorithm for online unit clustering

AU - Chan, Timothy M.

AU - Zarrabi-Zadeh, Hamid

N1 - Funding Information: Work of the first author has been supported in part by NSERC.

PY - 2009/7

Y1 - 2009/7

N2 - In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.

AB - In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.

KW - Online algorithms

KW - Randomized algorithms

KW - Unit clustering

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

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

U2 - 10.1007/s00224-007-9085-7

DO - 10.1007/s00224-007-9085-7

M3 - Article

AN - SCOPUS:70350675280

SN - 1432-4350

VL - 45

SP - 486

EP - 496

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -

A randomized algorithm for online unit clustering

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this