10 citations · 21 across the 16 of their papers we have counts for
4 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…
Bounding the chromatic number of dense digraphs by arc neighborhoods
Felix Klingelhoefer, Alantha Newman
The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is th…
Coloring tournaments with few colors: Algorithms and complexity
Felix Klingelhoefer, Alantha Newman
A -coloring of a tournament is a partition of its vertices into acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring…