14 citations · 51 across the 29 of their papers we have counts for
6 papers · 1 filter
A Local Search-Based Approach for Set Covering
Anupam Gupta, Euiwoong Lee, Jason Li
In the Set Cover problem, we are given a set system with each set having a weight, and we want to find a collection of sets that cover the universe, whilst having low total weight.…
Fitting Metrics and Ultrametrics with Minimum Disagreements
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee +1
Given recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the distance between and…
Correlation Clustering with Sherali-Adams
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
Given a complete graph where each edge is labeled or , the Correlation Clustering problem asks to partition into clusters to minimize the number of edges…
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 \…
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…
A Characterization of Approximability for Biased CSPs
Suprovat Ghoshal, Euiwoong Lee
A -biased Max-CSP instance with predicate is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative…