Fetching the paper…
Reading the bibliography…
We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) $k$-median and $k$-means in edge-weighted planar graphs; (3) $k$-means in Euclidean spaces of bounded dimension.
Heuristics for the fixed cost median problem
D. S. Hochbaum · 1982
Earlier work this paper cites.
Fast algorithms for shortest paths in planar graphs, with applications
G. N. Frederickson · 1987
Earlier work this paper cites.
A separator theorem for graphs with an excluded minor and its applications
N. Alon, P. D. Seymour, and R. Thomas · 1990
Earlier work this paper cites.
Approximation algorithms for NP-complete problems on planar graphs
B. Baker · 1994
Earlier work this paper cites.
Applications of weighted voronoi diagrams and randomization to variance-based k -clustering (extended abstract)
M. Inaba, N. Katoh, and H. Imai · 1994
Earlier work this paper cites.
Local Search in Combinatorial Optimization
E. Aarts and J. K. Lenstra, editors · 1997
Earlier work this paper cites.
Approximation algorithms for facility location problems
D. B. Shmoys, É. Tardos, and K. Aardal · 1997
Earlier work this paper cites.
Approximation schemes for Euclidean k -medians and related problems
S. Arora, P. Raghavan, and S. Rao · 1998
Earlier work this paper cites.
Greedy strikes back: Improved facility location algorithms
S. Guha and S. Khuller · 1999
Earlier work this paper cites.
Analysis of a local search heuristic for facility location problems
M. R. Korupolu, C. G. Plaxton, and R. Rajaraman · 2000
Earlier work this paper cites.
An approximation scheme for the uncapacitated facility location problem on planar graphs
A. A. Ageev · 2001
Earlier work this paper cites.
Approximation algorithms for metric facility location and k -median problems using the primal-dual schema and Lagrangian relaxation
K. Jain and V. Vazirani · 2001
Earlier work this paper cites.
Approximate clustering via core-sets
M. Bădoiu, S. Har-Peled, and P. Indyk · 2002
Earlier work this paper cites.
A new greedy approach for facility location problems
K. Jain, M. Mahdian, and A. Saberi · 2002
Earlier work this paper cites.
Clustering data streams: Theory and practice
S. Guha, A. Meyerson, N. Mishra, R. Motwani, and L. O’Callaghan · 2003
Earlier work this paper cites.
Embeddings and non-approximability of geometric problems
V. Guruswami and P. Indyk · 2003
Earlier work this paper cites.
Local search heuristics for k-median and facility location problems
V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit · 2004
Cited alongside, same era.
On coresets for k-means and k-median clustering
S. Har-Peled and S. Mazumdar · 2004
Cited alongside, same era.
A local search approximation algorithm for k-means clustering
T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu · 2004
Cited alongside, same era.
A simple linear time (1 + epsiv;)-approximation algorithm for k-means clustering in any dimensions
A. Kumar, Y. Sabharwal, and S. Sen · 2004
Cited alongside, same era.
Improved combinatorial algorithms for facility location problems
M. Charikar and S. Guha · 2005
Cited alongside, same era.
A PTAS for k-means clustering based on weak coresets
D. Feldman, M. Monemizadeh, and C. Sohler · 2007
A unified framework for approximating and clustering data
D. Feldman and M. Langberg · 2011
Later among the works it cites.
Improved spectral-norm bounds for clustering
P. Awasthi and O. Sheffet · 2012
Later among the works it cites.
Are stable instances easy?
Y. Bilu and N. Linial · 2012
Later among the works it cites.
Approximation algorithms for maximum independent set of pseudo-disks
T. M. Chan and S. Har-Peled · 2012
Later among the works it cites.
The effectiveness of Lloyd-type methods for the k-means problem
R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy · 2012
Later among the works it cites.
A 1.488 approximation algorithm for the uncapacitated facility location problem
S. Li · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Smaller coresets for k-median and k-means clustering
S. Har-Peled and A. Kushal · 2007
Cited alongside, same era.
A nearly linear-time approximation scheme for the euclidean k-median problem
S. G. Kolliopoulos and S. Rao · 2007
Cited alongside, same era.
Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
D. Arthur and S. Vassilvitskii · 2009
Cited alongside, same era.
Approximate clustering without the approximation
M. Balcan, A. Blum, and A. Gupta · 2009
Cited alongside, same era.
Stability yields a PTAS for k-median and k-means clustering
P. Awasthi, A. Blum, and O. Sheffet · 2010
Cited alongside, same era.
Parallel approximation algorithms for facility-location problems
G. E. Blelloch and K. Tangwongsan · 2010
Cited alongside, same era.
Approximating k-median via pseudo-approximation
S. Li and O. Svensson · 2013
Later among the works it cites.
Distributed balanced clustering via mapping coresets
M. Bateni, A. Bhaskara, S. Lattanzi, and V. S. Mirrokni · 2014
Later among the works it cites.
V. V. S. P. Bhattiprolu and S. Har-Peled · 2014
Later among the works it cites.
The hardness of approximation of Euclidean k-means
P. Awasthi, M. Charikar, R. Krishnaswamy, and A. K. Sinop · 2015
Later among the works it cites.
On variants of k-means clustering
S. Bandyapadhyay and K. R. Varadarajan · 2015
Later among the works it cites.
Effectiveness of local search for geometric optimization
V. Cohen-Addad and C. Mathieu · 2015
Later among the works it cites.
Approximation algorithms for polynomial-expansion and low-density graphs
S. Har-Peled and K. Quanrud · 2015
Later among the works it cites.
Clustering under perturbation resilience
M. Balcan and Y. Liang · 2016
Closest in time.
Local search yields a ptas for k-means in doubling metrics
Z. Friggstad, M. Rezapour, and M. R. Salavatipour · 2016
Closest in time.