Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Online Unit Clustering in Higher Dimensions
verfasst von : Adrian Dumitrescu, Csaba D. Tóth
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We revisit the online Unit Clustering problem in higher dimensions: Given a set of n points in \(\mathbb {R}^d\), that arrive one by one, partition the points into clusters (subsets) of diameter at most one, so as to minimize the number of clusters used. In this paper, we work in \(\mathbb {R}^d\) using the \(L_\infty \) norm. We show that the competitive ratio of any algorithm (deterministic or randomized) for this problem must depend on the dimension d. This resolves an open problem raised by Epstein and van Stee (WAOA 2008). 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\), \(d\in \mathbb {N}\), under \(L_{\infty }\) norm). We complement these results with some additional lower bounds for related problems in higher dimensions.