10 citations · 14 across the 13 of their papers we have counts for
8 papers · 1 filter
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…