3 papers
cs.DS2026
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
We give a new dual fitting algorithm which gives improved approximation ratios of and for -Means in (high-dimensional) Euclidean and genera…
cs.DS2026
An Improved Greedy Approximation for (Metric) -Means
Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao +3
Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the -Means…
cs.DS2023
Improved Approximations for Ultrametric Violation Distance
Moses Charikar, Ruiquan Gao
We study the Ultrametric Violation Distance problem introduced by Cohen-Addad, Fan, Lee, and Mesmay [FOCS, 2022]. Given pairwise distances a…