10 citations · 12 across the 12 of their papers we have counts for
8 papers · 1 filter
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…
Fitting Metrics and Ultrametrics with Minimum Disagreements
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee +1
Given recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the distance between and…
On Some Variants of Euclidean K-Supplier
Euiwoong Lee, Viswanath Nagarajan, Lily Wang
The -Supplier problem is an important location problem that has been actively studied in both general and Euclidean metrics. Many of its variants have also been studied, primari…