16 citations · 45 across the 22 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.CC2018
Improved Inapproximability of Rainbow Coloring
Per Austrin, Amey Bhangale, Aditya Potukuchi
A rainbow -coloring of a -uniform hypergraph is a -coloring of the vertex set such that every hyperedge contains all colors. We prove that given a rainbow $(k - 2\lflo…
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…