Online unit clustering in higher dimensions

DOI10.1007/978-3-319-89441-6_18zbMATH Open1504.68289arXiv1708.02662OpenAlexW2743825404MaRDI QIDQ1644944FDOQ1644944

Authors: Adrian Dumitrescu, Csaba D. Tóth 

Publication date: 22 June 2018

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 $mathbb{R}^d$ using the $L_{i}nfty$ 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 $mathbb{Z}^d$, $dinmathbbN$, under $L_{infty}$ 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.

Full work available at URL: https://arxiv.org/abs/1708.02662

Recommendations

• Online unit clustering and unit covering in higher dimensions
• Better bounds on online unit clustering
• Better bounds on online unit clustering
• On the Online Unit Clustering Problem
• On the online unit clustering problem
• Online unit clustering: Variations on a theme
• An Improved Algorithm for Online Unit Clustering
• An improved algorithm for online unit clustering
• A randomized algorithm for online unit clustering
• A Randomized Algorithm for Online Unit Clustering

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (6)

• An online 2-dimensional clustering problem with variable sized clusters
• A Randomized Algorithm for Online Unit Clustering
• Online unit clustering: Variations on a theme
• An improved algorithm for online unit clustering
• Online unit clustering and unit covering in higher dimensions
• A new model for the linear 1-dimensional online clustering problem

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)