Clustering to Minimize the Maximum Intercluster Distance

By Teofilo F. Gonzalez. 1985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Variational Continual Learning (2017, methodology): “Alternatively, the greedy K -center algorithm (Gonzalez, 1985) can be used to return K data points that are guaranteed to be spread throughout the input space.”
Proportionally Fair Clustering (2019, background): “sic context for clustering work (Gonzalez, 1985; Shmoys et al., 1997; Charikar et al., 2002; Arya et al., 2004), and is perhaps best known as the setting for the celebrated k-means heuristic (independently discovered many times, see (Jain, 2010) for a brief history).”
Bayesian Structure Adaptation for Continual Learning (2019, methodology): “Coreset selection can be done either through random selection or K -center greedy algorithm (Gonzalez, 1985).”
A Wholistic View of Continual Learning with Deep Neural Networks: Forgotten Lessons and the Bridge to Active and Open World Learning (2020, methodology): “Greedy k-center: greedy k-center approximation (Gonzalez, 1985) for core set selection as used in A kernel density estimate of the per class aggregate posterior (in color) and the corresponding distributional approximation of the selected core set elements (dashed black) are added on each dimension.”
Fair Clustering Through Fairlets (2018, methodology): “This, combined with the fact that the best approximation algorithm for k -center yields a 2 -approximation (Gonzalez, 1985), gives us the following.”
Unsupervised Learning Methods for Molecular Simulation Data (2021, background): “247 The objective of k -centers is to maximize the distance between cluster centers.”
The Design of Approximation Algorithms (2011, unknown): “2 is due to Gonzalez [141].”
A Survey of Clustering Data Mining Techniques (2006, background): “Maximum of intra-cluster variances, instead of the sum, can serve as an objective function [95].”
Improved fast gauss transform and efficient kernel density estimation (2003, methodology): “Gonzalez [12] proved that farthest-point clustering is a 2approximation algorithm which computes a partition with maximum radius at most twice the optimum.”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, methodology): “First, each node vi clusters its local dataset Ai into mi groups using the classic greedy m-center algorithm of Gonzalez (1985), which repeatedly adds a new center that is farthest from the current set of centers (Algorithm 4).”
Geometric Approximation via Coresets (2007, methodology): “In order to construct S efficiently, we use Gonzalez’s greedy algorithm [32] to compute a factor-2 approximation of k-center, which returns a value r̃ ≤ 2r∗.”
Scalable sparse approximation of a sample mean (2014, methodology): “The algorithm is described in Algorithm 1 [20].”
Routing in Socially Selfish Delay Tolerant Networks (2010, methodology): “To address this problem, we combine KNN with the Kcenter algorithm [19] to propose a two-phase solution:”