14 citations · 51 across the 29 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
Optimal Bounds for the -cut Problem
Anupam Gupta, David G. Harris, Euiwoong Lee +1
In the -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into connected components. Algorithms of Karger \& Stein can s…