24 citations · 151 across the 43 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2018★ 1 cited
Near-optimal approximation algorithm for simultaneous Max-Cut
Amey Bhangale, Subhash Khot, Swastik Kopparty +2
In the simultaneous Max-Cut problem, we are given weighted graphs on the same set of vertices, and the goal is to find a cut of the vertex set so that the minimum, over the…
cs.CC2011
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
Sushant Sachdeva, Rishi Saket
We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k = 2), the minimum vertex cover c…