finding maximum weight subgraph My graph is as follows:


I need to find a maximum weight subgraph.

The problem is as follows:

There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in different Vertex cluster, there is a weighted edge, and in the same Vextex cluster, there is no edge among vertexes. Now I want to find a maximum weight subgraph by finding only one vertex in each Vertex cluster. And the total weight is computed by adding all weights of the edges between the selected vertex. I add a picture to explain the problem. Now I know how to model this problem by ILP method. However, I do not know how to solve it by an approximation algorithm and how to get its approximation ratio.

Could you give some solutions and suggestions?

Thank you very much. If any unclear points in this description, please feel free to ask.
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 to a factor of $O(\log n)$, the weights can be taken care of by a standard bucketing argument. Up to a factor of $2$, the graph can be made bipartite by randomly assigning each cluster one of two sets (say $A$ or $B$) according to a fair coin toss, and removing any edges that go from $A$ to $B$. So this gives an immediate $O(n^{1/3} \log n)$ approximation algorithm, using the algorithm of CHK as a subroutine. 

The previous hardness of $O(2^{\log^{1-\epsilon} n})$ carries through (again, see the Kortsarz paper for more details), and there are some conjectures out there that for some $\epsilon&gt;0$, the problem is hard to approximate to within $O(n^{\epsilon})$.