Fetching the paper…
Reading the bibliography…
For a certain class of distributions, we prove that the linear programming relaxation of $k$-medoids clustering---a variant of $k$-means clustering where means are replaced by exemplars from within the dataset---distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn and the separation distance between any two balls are sufficiently large.
J. A. Hartigan and M. A. Wong, “Algorithm as 136: A k-means clustering algorithm,” Journal of the Royal Statistical Society. Series C (Applied Statistics)
1979
Earlier work this paper cites.
C. H. Papadimitriou, “Worst-case and probabilistic analysis of a geometric location problem,” SIAM Journal on Computing
1981
Earlier work this paper cites.
S. Lloyd, “Least squares quantization in PCM,” Information Theory, IEEE Transactions on
1982
Earlier work this paper cites.
P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,” Social networks
1983
Earlier work this paper cites.
N. Megiddo and K. J. Supowit, “On the complexity of some common geometric location problems,” SIAM journal on computing
1984
Earlier work this paper cites.
P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman, “Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection,” Pattern Analysis and Machine Intelligence, IEEE Transactions on
1997
Earlier work this paper cites.
D. B. Shmoys, É. Tardos, and K. Aardal, “Approximation algorithms for facility location problems,” in Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
1997
Earlier work this paper cites.
S. de Vries, M. Posner, and R. Vohra, “The k-median problem on a tree,” tech. rep., Citeseer, 1998
1998
Earlier work this paper cites.
S. Guha and S. Khuller, “Greedy strikes back: Improved facility location algorithms,” in Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms
1998
Earlier work this paper cites.
M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, “Analysis of a local search heuristic for facility location problems,” in Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms
1998
Earlier work this paper cites.
S. Dasgupta, “Learning mixtures of Gaussians,” in Foundations of Computer Science, 1999. 40th Annual Symposium on
1999
Earlier work this paper cites.
M. Charikar and S. Guha, “Improved combinatorial algorithms for the facility location and k-median problems,” in Foundations of Computer Science, 1999. 40th Annual Symposium on
1999
Earlier work this paper cites.
A. Condon and R. M. Karp, “Algorithms for graph partitioning on the planted partition model,” Random Structures and Algorithms
2001
Earlier work this paper cites.
A. Sanjeev and R. Kannan, “Learning mixtures of arbitrary gaussians,” in Proceedings of the thirty-third annual ACM symposium on Theory of computing
2001
Earlier work this paper cites.
M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani, “A greedy facility location algorithm analyzed using dual fitting,” in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques
2001
Earlier work this paper cites.
K. Jain, M. Mahdian, and A. Saberi, “A new greedy approach for facility location problems,” in Proceedings of the thirty-fourth annual ACM symposium on Theory of Computing
2002
Earlier work this paper cites.
M. Van der Laan, K. Pollard, and J. Bryan, “A new partitioning around medoids algorithm,” Journal of Statistical Computation and Simulation
2003
Earlier work this paper cites.
F. A. Chudak and D. B. Shmoys, “Improved approximation algorithms for the uncapacitated facility location problem,” SIAM Journal on Computing
2003
Earlier work this paper cites.
K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, “Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp,” Journal of the ACM (JACM)
2003
Earlier work this paper cites.
N. Bansal, A. Blum, and S. Chawla, “Correlation clustering,” Machine Learning
2004
Cited alongside, same era.
S. Vempala and G. Wang, “A spectral algorithm for learning mixture models,” Journal of Computer and System Sciences
2004
Cited alongside, same era.
V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit, “Local search heuristics for k-median and facility location problems,” SIAM Journal on Computing
2004
Cited alongside, same era.
R. Kannan, H. Salmasian, and S. Vempala, “The spectral method for general mixture models,” in Learning Theory
2005
Cited alongside, same era.
D. Achlioptas and F. McSherry, “On spectral learning of mixtures of distributions,” in Learning Theory
2005
Cited alongside, same era.
S. C. Brubaker, “Robust PCA and clustering in noisy mixtures,” in Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms
2009
Later among the works it cites.
2009
Later among the works it cites.
2009
Later among the works it cites.
C. Boutsidis, A. Zouzias, and P. Drineas, “Random projections for k k -means clustering,” in Proc. NIPS
2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Forschungsinstitut für Diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität, 2005
J. Vygen, Approximation Algorithms Facility Location Problems · 2005
Cited alongside, same era.
J. Feldman, R. A. Servedio, and R. O’Donnell, “PAC learning axis-aligned mixtures of gaussians with no separation assumption,” in Learning Theory
2006
Cited alongside, same era.
M. Sviridenko, “An improved approximation algorithm for the metric uncapacitated facility location problem,” in Integer programming and combinatorial optimization
2006
Cited alongside, same era.
M. Mahdian, Y. Ye, and J. Zhang, “Approximation algorithms for metric facility location problems,” SIAM Journal on Computing
2006
Cited alongside, same era.
B. J. Frey and D. Dueck, “Clustering by passing messages between data points,” Science
2007
Cited alongside, same era.
M. Mézard, “Computer science. where are the exemplars?,” Science (New York, NY)
2007
Cited alongside, same era.
M. Leone, M. Weigt, et al
2007
Cited alongside, same era.
2010
Later among the works it cites.
A. T. Kalai, A. Moitra, and G. Valiant, “Efficiently learning mixtures of two gaussians,” in Proceedings of the 42nd ACM symposium on Theory of computing
2010
Later among the works it cites.
M. Belkin and K. Sinha, “Polynomial learning of distribution families,” in Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
2010
Later among the works it cites.
U. Bodenhofer, A. Kothmeier, and S. Hochreiter, “Apcluster: an R package for affinity propagation clustering,” Bioinformatics
2011
Later among the works it cites.
2011
Later among the works it cites.
2011
Later among the works it cites.
2012
Later among the works it cites.
2012
Later among the works it cites.
Y. Chen, S. Sanghavi, and H. Xu, “Clustering sparse graphs,” arXiv preprint arXiv:1210.3335
2012
Later among the works it cites.
2012
Later among the works it cites.
E. Elhamifar, G. Sapiro, and R. Vidal, “Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery,” in Advances in Neural Information Processing Systems
2012
Later among the works it cites.
S. Li, “A 1.488 approximation algorithm for the uncapacitated facility location problem,” Information and Computation
2012
Later among the works it cites.
2013
Closest in time.
S. Li and O. Svensson, “Approximating k-median via pseudo-approximation,” in Proceedings of the 45th annual ACM symposium on Symposium on theory of computing
2013
Closest in time.