New answers tagged

1

The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.


1

This is the weighted, non-bipartite generalization of the Max-Rep problem, which is equivalent to LabelCover-Max. See Page 20 of Kortsarz. As far as I know, the best approximation algorithm to that problem is $O(n^{1/3})$, due to Charikar, Hajiaghayi, and Karloff In terms of approximation, the original Max-Rep problem and your generalization are similar. Up ...


Top 50 recent answers are included