Abstract
We reprove three known algorithmic bounds for terminalclustering problems, using a single framework that leads to simpler proofs. In this genre of problems, the input is a metric space (X,d) (possibly arising from a graph) and a subset of terminals K subset X, and the goal is to partition the points X such that each part, called a cluster, contains exactly one terminal (possibly with connectivity requirements) so as to minimize some objective. The three bounds we reprove are for Steiner Point Removal on trees [Gupta, SODA 2001], for Metric 0Extension in bounded doubling dimension [Lee and Naor, unpublished 2003], and for Connected Metric 0Extension [Englert et al., SICOMP 2014].
A natural approach is to cluster each point with its closest terminal, which would partition X into socalled Voronoi cells, but this approach can fail miserably due to its stringent cluster boundaries. A nowstandard fix, which we call the RelaxedVoronoi framework, is to use enlarged Voronoi cells, but to obtain disjoint clusters, the cells are computed greedily according to some order. This method, first proposed by Calinescu, Karloff and Rabani [SICOMP 2004], was employed successfully to provide stateoftheart results for terminalclustering problems on general metrics. However, for restricted families of metrics, e.g., trees and doubling metrics, only more complicated, adhoc algorithms are known. Our main contribution is to demonstrate that the RelaxedVoronoi algorithm is applicable to restricted metrics, and actually leads to relatively simple algorithms and analyses.
BibTeX  Entry
@InProceedings{filtser_et_al:OASIcs:2018:10036,
author = {Arnold Filtser and Robert Krauthgamer and Ohad Trabelsi},
title = {{Relaxed Voronoi: A Simple Framework for TerminalClustering Problems}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {10:110:14},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770996},
ISSN = {21906807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10036},
URN = {urn:nbn:de:0030drops100369},
doi = {10.4230/OASIcs.SOSA.2019.10},
annote = {Keywords: Clustering, Steiner point removal, Zero extension, Doubling dimension, Relaxed voronoi}
}
Keywords: 

Clustering, Steiner point removal, Zero extension, Doubling dimension, Relaxed voronoi 
Seminar: 

2nd Symposium on Simplicity in Algorithms (SOSA 2019) 
Issue Date: 

2018 
Date of publication: 

18.12.2018 