From the 1 of 10 linked papers with an AI index.
10 papers
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
The paper introduces a new dual‑fitting algorithm that achieves better approximation ratios for the k‑means clustering problem in both Euclidean and general metric spaces, using a…
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…
A -Approximation Algorithm for Metric -Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +2
In the classical NP-hard metric -median problem, we are given a set of clients and centers with metric distances between them, along with an integer parameter . The…
Static to Dynamic Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +7
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to clu…
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +1
The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients and a set of facilities in a metric space $(C \…