3 papers
cs.DS2022
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee +1
We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds. - W…
cs.CC2020
On Approximability of Clustering Problems Without Candidate Centers
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
The k-means objective is arguably the most widely-used cost function for modeling clustering tasks in a metric space. In practice and historically, k-means is thought of in a conti…
cs.DS2019
Tight FPT Approximations for -Median and -Means
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar +2
We investigate the fine-grained complexity of approximating the classical -median / -means clustering problems in general metric spaces. We show how to improve the approximat…