Online unit clustering in higher dimensions

Abstract: We revisit the online Unit Clustering and Unit Covering problems in higher dimensions: Given a set of

n

points in a metric space, that arrive one by one, Unit Clustering asks to partition the points into the minimum number of clusters (subsets) of diameter at most one; while Unit Covering asks to cover all points by the minimum number of balls of unit radius. In this paper, we work in

m a t h b b R^{d}

using the

L_{i} n f t y

norm. We show that the competitive ratio of any online algorithm (deterministic or randomized) for Unit Clustering must depend on the dimension

d

. We also give a randomized online algorithm with competitive ratio

O (d^{2})

for Unit Clustering of integer points (i.e., points in

m a t h b b Z^{d}

,

d i n m a t h b b N

, under

L_{i n f t y}

norm). We show that the competitive ratio of any deterministic online algorithm for Unit Covering is at least

2^{d}

. This ratio is the best possible, as it can be attained by a simple deterministic algorithm that assigns points to a predefined set of unit cubes. We complement these results with some additional lower bounds for related problems in higher dimensions.

Recommendations

Cited in

(6)

This page was built for publication: Online unit clustering in higher dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1644944)