4 citations · 6 across the 8 of their papers we have counts for
18 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.…
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…
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee
We present hardness of approximation results for Correlation Clustering with local objectives and for Hierarchical Clustering with dissimilarity information. For the former, we stu…
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
Jungho Ahn, Eun Jung Kim, Euiwoong Lee
For a family of graphs , Weighted -Deletion is the problem for which the input is a vertex weighted graph and the goal is to delete $S\subseteq…
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee +1
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We surve…