14 citations · 51 across the 29 of their papers we have counts for
43 papers
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
Suprovat Ghoshal, Euiwoong Lee
A -constrained Boolean Max-CSP instance is a Boolean Max-CSP instance on predicate where the objective is to find a labeling of relative weight ex…
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…