New answers tagged approximation-algorithms
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
