We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight.

enter image description here

We use a greedy algorithm that takes in each step maximum weighted vertex and adds it to the set and removes all the adjacent vertices to the vertex. I want to prove that algorithm is 6-approximation.

Let $W^*$ be optimal solution $O$, and $W$ be greedy solution $S$. We build a mapping for each $u \in O$ and we define $u'=u$ if $u\in S$ else $u'=$ $"u$ neighbor" in $S$, that means at some iteration in greedy algorithm the $u$ was excluded and the $u$ neighbour $w(u) \leqslant w(u')$ was chosen.

$W^* = \displaystyle\sum_{u \in O} w(u) \leqslant \displaystyle\sum_{u' \in S} w(u') $.

Afterwards I'm bit confused how to prove that it's 6-approximation, as in each step when we select vertex from S, we remove only at most 3 vertices from O, based on the graph. I understand that it's 1/6 because of the number of neighbours of vertex, but I'm bit confused about that choosing non-optimal vertex can remove up to 3 vertices only.

  • 1
    $\begingroup$ Let $u$ be the max-weight vertex. You can either select $u$ or not select $u$. If you select $u$, then you gain $w(u)$. If you don't select $u$, then what's the maximum possible gain you can get? In the best case, you can select all its neighbors, and gain $\sum_{v \in N(u)} w(v) \le \sum_{v \in N(u)} w(u) \le 6 w(u)$. Then you should note that the remaining graph in the first case is $G \setminus N'(u)$ (where $N'(u) = N(u) \cup \{u\}$), and in the second case - $G \setminus \cup_{v \in N(u)} N'(v)$, so the first graph includes the second one. The rest should be simple. $\endgroup$ – user114966 May 7 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.