10 citations · 14 across the 13 of their papers we have counts for
20 papers
Pseudometric-Weighted Correlation Clustering via Spectral Preclustering
Chenglin Fan, Dahoon Lee, Euiwoong Lee
We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For e…
Complexity of Local Search for CSPs Parameterized by Constraint Difference
Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi +4
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization…
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
Dahoon Lee, Chenglin Fan, Euiwoong Lee
Chromatic Correlation Clustering (CCC) generalizes Correlation Clustering by assigning multiple categorical relationships (colors) to edges and imposing chromatic constraints on th…
Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
Chenglin Fan, Dahoon Lee, Euiwoong Lee
Correlation Clustering (CC) is a foundational problem in unsupervised learning that models binary similarity relations using labeled graphs. While classical CC has been widely stud…
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
Aditya Anand, Euiwoong Lee, Jason Li +1
Given a directed graph with vertices and edges, a parameter and two disjoint subsets , we show that the number of all-subsets important separato…
Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
Aditya Anand, Euiwoong Lee, Davide Mazzali +1
This paper studies complete -Constraint Satisfaction Problems (CSPs), where an -variable instance has exactly one nontrivial constraint for each subset of variables, i.e.…
Static to Dynamic Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +7
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to clu…
Solving the Correlation Cluster LP in Sublinear Time
Nairen Cao, Vincent Cohen-Addad, Shi Li +7
Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizi…
Min-CSPs on Complete Instances
Aditya Anand, Euiwoong Lee, Amatya Sharma
Given a fixed arity , Min--CSP on complete instances involves a set of variables and one nontrivial constraint for every -subset of variables (so there are…
Asymptotically Optimal Hardness for -Set Packing and -Matroid Intersection
Euiwoong Lee, Ola Svensson, Theophile Thiery
For any , we prove that -Dimensional Matching is hard to approximate within a factor of for large unless $\textsf{NP} \subseteq \text…
Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand, Euiwoong Lee, Jason Li +2
Unbreakable decomposition, introduced by Cygan et al. (SICOMP'19) and Cygan et al. (TALG'20), has proven to be one of the most powerful tools for parameterized graph cut problems i…
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on variables and alphab…
Understanding the Cluster LP for Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +3
In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla (FOCS 2002), the input is a complete graph where edges are labeled either or , and the g…
Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee, Jason Li +1
We study polynomial-time approximation algorithms for (edge/vertex) Sparsest Cut and Small Set Expansion in terms of , the number of edges or vertices cut in the optimal solutio…
Max-Cut with -Accurate Predictions
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +2
We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are give…
Separating -Median from the Supplier Version
Aditya Anand, Euiwoong Lee
Given a metric space along with an integer , the -Median problem asks to open centers to minimize , where $d(v, C) := \mi…
A PTAS for -Low Rank Approximation: Solving Dense CSPs over Reals
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4
We consider the Low Rank Approximation problem, where the input consists of a matrix and an integer , and the goal is to find a matrix of…
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
Vincent Cohen-Addad, Euiwoong Lee, Shi Li +1
We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either or , the goal is to find a partition of the vertices that mini…
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
Euiwoong Lee, Pasin Manurangsi
We consider the question of approximating Max 2-CSP where each variable appears in at most constraints (but with possibly arbitrarily large alphabet). There is a simple $(\frac…