<p>This is the weighted, non-bipartite generalization of the Max-Rep problem, which is equivalent to LabelCover-Max. See Page 20 of <a href="https://crab.rutgers.edu/~guyk/pub/hard/nabs.pdf" rel="nofollow noreferrer">Kortsarz</a>. As far as I know, the best approximation algorithm to that problem is <span class="math-container">$O(n^{1/3})$</span>, due to <a href="http://www-math.mit.edu/~hajiagha/LabelCover.pdf" rel="nofollow noreferrer">Charikar, Hajiaghayi, and Karloff</a></p>

<p>In terms of approximation, the original Max-Rep problem and your generalization are similar. Up to a factor of <span class="math-container">$O(\log n)$</span>, the weights can be taken care of by a standard bucketing argument. Up to a factor of <span class="math-container">$2$</span>, the graph can be made bipartite by randomly assigning each cluster one of two sets (say <span class="math-container">$A$</span> or <span class="math-container">$B$</span>) according to a fair coin toss, and removing any edges that go from <span class="math-container">$A$</span> to <span class="math-container">$B$</span>. So this gives an immediate <span class="math-container">$O(n^{1/3} \log n)$</span> approximation algorithm, using the algorithm of CHK as a subroutine. </p>

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

CC BY-SA 4.0
2019-06-26T14:36:05.267Z
Thanks for your nice answer and sorry for that I have some problems.  I am confused about the process of transforming this question into the Max-Rep problem. I do not understand how we could transform the weight by a factor O(logn). After we assign cluster to A or B, A and B may consist of n/2 clusters (may be bigger than 2) and the clusters in the same set are connected by many edges, so I also confused why we could apply the CHK as the subroutine?                                                                       Sorry for these stupid questions. Thanks!
Refrain
CC BY-SA 4.0
2019-06-26T21:28:08.203Z
The bucketing argument works as follows. With only a constant-factor loss, we  throw out all edges with weight less than $w_{\max} / n^2$. For each $r \in \{0, 1, 2, \cdots, \lceil 2 \log_2\ n \} \rceil$, let $E_r$ be the set of edges with weight between $2^r w_\min$ and $2^{r+1} w_\min$. This forms a partition of all edges, putting each into one of $O(\log n)$ buckets. The problem restricted to $G=(V,E_r)$ has all weights that are within a factor of $2$ of each other, so treating this as an unweighted problem gives a $\tfrac{1}{2}$-approximation to the optimal solution (for that problem). ...
Yonatan N
CC BY-SA 4.0
2019-06-26T21:28:51.647Z
...  Since there are only $O(\log n)$ buckets, at least one of these buckets has a solution with objective value $\Omega(\textrm{OPT}/\log n)$. So the algorithm here is to use CHK as a subroutine on each of the $O(\log n)$ buckets and return the one with the largest objective score, which  has a lower bound of $\tfrac{1}{2} \Omega(\textrm{OPT}/\log n) = \Omega(\textrm{OPT}/\log n)$  on its performance.
Yonatan N
CC BY-SA 4.0
2019-06-26T21:42:53.777Z
The factor-2 reduction to the bipartite case randomly assigns each vertex cluster to one of two sides of a bipartition $(A,B)$. Let's consider the approach that works by randomly choosing $n/2$ vertex clusters for $A$, and the other $n/2$ go to $B$. We then just discard *all* edges between two clusters in $A$ and between any two clusters in $B$, leaving only edges that go between clusters in A and those in B. Let $\textrm{OPT}_1$ be the set of edges in the original optimal solution, and $\textrm{OPT}_2 \subseteq \textrm{OPT}_1$  be the edges that survived our discarding procedure. ...
Yonatan N
CC BY-SA 4.0
2019-06-26T21:43:00.723Z
... For an edge in $\textrm{OPT}_1$, what is its contribution to $\textrm{OPT}_2$? Well, for any such edge $e$, it survives the discarding procedure with probability at least $1/2$, so in expectation it contributes at least $w_e / 2$ to the total weight of $\textrm{OPT}_2$. Summing over all edges in $\textrm{OPT}_1$, one can use linearity of expectations to conclude that $E[w(\textrm{OPT}_2)] \geq w(\textrm{OPT}_1) / 2$, so the loss incurred by such a procedure is at most some multiplicative constant.
Yonatan N
CC BY-SA 4.0
2019-06-25T19:41:26.587Z
2019-06-25T19:41:26.587Z
Yonatan N
<p>My graph is as follows:
<a href="https://i.sstatic.net/CUnJV.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CUnJV.jpg" alt="enter image description here"></a></p>

<p>I need to find a maximum weight subgraph.</p>

<p>The problem is as follows:</p>

<p>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.</p>

<p>Could you give some solutions and suggestions?</p>

<p>Thank you very much. If any unclear points in this description, please feel free to ask.</p>

CC BY-SA 4.0
2019-06-25T20:37:14.897Z
Probably a local search may be a good heuristic to try here: given a current solution $S$, you find a cluster $C$ and a vertex $c'$ in this cluster such that weight$(S\setminus c \cup c')>$ weight$(S)$ where $c$ was the vertex in $C\cap S$
Mathieu Mari
<graph-theory><graph-algorithms><approximation-algorithms><linear-programming>
finding maximum weight subgraph
Refrain
# finding maximum weight subgraph

(Asked by: username_0 on 2019-06-25)

My graph is as follows:
[![enter image description here](https://i.sstatic.net/CUnJV.jpg)](https://i.sstatic.net/CUnJV.jpg)

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.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, linear-programming
> **Comments:**
> **username_1**: Probably a local search may be a good heuristic to try here: given a current solution $S$, you find a cluster $C$ and a vertex $c'$ in this cluster such that weight$(S\setminus c \cup c')>$ weight$(S)$ where $c$ was the vertex in $C\cap S$  

---

## 1 answers

### Answer by username_2 on 2019-06-25. Score: 2 | Accepted answer

This is the weighted, non-bipartite generalization of the Max-Rep problem, which is equivalent to LabelCover-Max. See Page 20 of [Kortsarz](https://crab.rutgers.edu/~guyk/pub/hard/nabs.pdf). As far as I know, the best approximation algorithm to that problem is $O(n^{1/3})$, due to [Charikar, Hajiaghayi, and Karloff](http://www-math.mit.edu/~hajiagha/LabelCover.pdf)

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>0$, the problem is hard to approximate to within $O(n^{\epsilon})$.

> **Comments:**
> **username_0**: Thanks for your nice answer and sorry for that I have some problems.  I am confused about the process of transforming this question into the Max-Rep problem. I do not understand how we could transform the weight by a factor O(logn). After we assign cluster to A or B, A and B may consist of n/2 clusters (may be bigger than 2) and the clusters in the same set are connected by many edges, so I also confused why we could apply the CHK as the subroutine?                                                                       Sorry for these stupid questions. Thanks!  
> **username_2**: The bucketing argument works as follows. With only a constant-factor loss, we  throw out all edges with weight less than $w_{\max} / n^2$. For each $r \in \{0, 1, 2, \cdots, \lceil 2 \log_2\ n \} \rceil$, let $E_r$ be the set of edges with weight between $2^r w_\min$ and $2^{r+1} w_\min$. This forms a partition of all edges, putting each into one of $O(\log n)$ buckets. The problem restricted to $G=(V,E_r)$ has all weights that are within a factor of $2$ of each other, so treating this as an unweighted problem gives a $\tfrac{1}{2}$-approximation to the optimal solution (for that problem). ...  
> **username_2**: ...  Since there are only $O(\log n)$ buckets, at least one of these buckets has a solution with objective value $\Omega(\textrm{OPT}/\log n)$. So the algorithm here is to use CHK as a subroutine on each of the $O(\log n)$ buckets and return the one with the largest objective score, which  has a lower bound of $\tfrac{1}{2} \Omega(\textrm{OPT}/\log n) = \Omega(\textrm{OPT}/\log n)$  on its performance.  
> **username_2**: The factor-2 reduction to the bipartite case randomly assigns each vertex cluster to one of two sides of a bipartition $(A,B)$. Let's consider the approach that works by randomly choosing $n/2$ vertex clusters for $A$, and the other $n/2$ go to $B$. We then just discard *all* edges between two clusters in $A$ and between any two clusters in $B$, leaving only edges that go between clusters in A and those in B. Let $\textrm{OPT}_1$ be the set of edges in the original optimal solution, and $\textrm{OPT}_2 \subseteq \textrm{OPT}_1$  be the edges that survived our discarding procedure. ...  
> **username_2**: ... For an edge in $\textrm{OPT}_1$, what is its contribution to $\textrm{OPT}_2$? Well, for any such edge $e$, it survives the discarding procedure with probability at least $1/2$, so in expectation it contributes at least $w_e / 2$ to the total weight of $\textrm{OPT}_2$. Summing over all edges in $\textrm{OPT}_1$, one can use linearity of expectations to conclude that $E[w(\textrm{OPT}_2)] \geq w(\textrm{OPT}_1) / 2$, so the loss incurred by such a procedure is at most some multiplicative constant.  

---

