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