0
$\begingroup$

I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given:

  • A digraph G = (V,E) with wv being the weight on vertex v for every v ∈ V.
  • A multi-set S is a set such that it contains elements more than one time. Suppose from a directed edge e = (u,v) either u is in S atleast one time or v is in S atleast 2 times.
  • The weight of the set S is the sum of all the vertices in it, vertices that appear multiple times also appear in the sum multiple times.

I have to write an IP for finding the multi-set that d-covers and minimizes the weight, relax it to LP and provide a rounding scheme that guarantees 2-approximation to the best multi-set


My proposed solution:

For IP:

min     Σv∈V wv . xv
s.t        xu + 2xv ≥ 1        ∀ {u,v} ∈ Σe∈S
           xu + 2xv ∈ {0,1}

Relaxed LP:
min     Σv∈V wv . xv
s.t        0 < xu + 2xv ≤ 1        ∀ {u,v} ∈ Σe∈S
           OPT ≥ Σv∈V wv . xv


Apart from this, I have to also write a rounding scheme that guarantees a 2-Approximation to the best multiset. Which I don't understand how to approach.

Your kind help would be appreciated in correcting my solution and with the rounding scheme.

Thank you in advance.

$\endgroup$

1 Answer 1

0
$\begingroup$

I think there is a problem in the definition of your IP and LP systems.

If $x_u$ represents the number of times you can select a vertex $u$ in the multiset $S$, then you want to verify the following conditions:

  • For an edge $(u, v)\in E$, either $x_u \geqslant 1$ or $x_v \geqslant 2$. That means that $x_u + \frac{x_v}2\geqslant 1$ (or equivalently $2x_u + x_v\geqslant 2$). There lies your first error, since you wrote $x_u + 2x_v\geqslant 1$ instead.
  • Since you used "at least" in the description of the previous condition, the lines $x_u+2x_v\in \{0,1\}$ in the IP system and $0<x_u+2x_v\leqslant 1$ in the LP system are wrong. Nothing prevents you to have a $x_u$ greater than $1$, and $x_u+2x_v$ could even be equal up to $6$ (see below).
  • If you want an upper bound, it would be on $x_u$ (and $x_v$), not on the sum. For the IP, it would be $x_u\in \{0,1,2\}$ and for the LP it would be $0\leqslant x_u \leqslant 2$.

To summarize:

  • IP:

    Minimize $\sum\limits_{v\in V}x_vw_v$.

    s.t. $2x_u + x_v\geqslant 2$ for $(u, v)\in E$

    and $x_v \in \{0,1,2\}$ for $v\in V$

  • LP relaxation:

    Minimize $\sum\limits_{v\in V}x_vw_v$.

    s.t. $2x_u + x_v\geqslant 2$ for $(u, v)\in E$

    and $0\leqslant x_v \leqslant 2$ for $v\in V$

Now suppose you want to compute a solution (not necessarily optimal) to the IP system. Using the LP relaxation, a way to do it is the following:

  • compute an optimal solution $X =\{x_v\mid v\in V\}$ to the LP relaxation;
  • consider $y_v = \left\{\begin{array}{ll}0 & \text{if }x_v< 0.5\\1&\text{if }0.5\leqslant x_v\leqslant 1\\2&\text{otherwise} \end{array}\right.$
  • then $Y = \{y_v \mid v\in V\}$ is a solution (not necessarily optimal) to the IP system.

To show the last claim, we need to verify that the $y_v$ still satisfy the conditions :

  • $y_v \in \{0, 1,2\}$ by definition;
  • for $(u, v)\in E$, $2x_u + x_v \geqslant 2$. Let us distinguish:
    • if $x_u \geqslant 0.5$, then $y_u = 1$ and $2y_u + y_v \geqslant 2$;
    • otherwise, $x_u < 0.5$ and $x_v \geqslant 2 - 2x_u > 2 - 1 = 1$, and $y_v = 2$, so $2y_u + y_v \geqslant 2$.

Finally, we want to prove that this is a $2$-approximation. Assume $X^* = \{x_v^*\mid v\in V\}$ is an optimal solution to the IP system. Since $X^*$ is also a (non necessarily optimal) solution to the LP system, then: $$\sum\limits_{v\in V} x_vw_v \leqslant \sum\limits_{v\in V}x^*_vw_v$$ But given the definition of $y_v$, we have $y_v\leqslant 2x_v$. That means that: $$\sum\limits_{v\in V} y_vw_v \leqslant 2\sum\limits_{v\in V}x^*_vw_v$$ We conclude that this is indeed a $2$-approximation.

To find the right formula for $y_v$, it was a bit of a trial-and-error process:

  • my first intuition was to try to round $x_v$ to the nearest integer: $y_v = \left\lceil x_v - \frac12\right\rceil$. However, that did not guarantee that $2y_u + y_v\geqslant 2$ for $(u, v)\in E$ (for example, $x_u = 0.4$ and $x_v = 1.2$ satisfies $2x_u + x_v \geqslant 2$, but we would have $y_u = 0$ and $y_v = 1$);
  • my second try was to round $x_v$ up: $y_v = \left\lceil x_v\right\rceil$. While this would give a valid solution, it would not be a $2$-approximation;
  • my third try was to consider $y_v = \left\lceil x_v - \frac13\right\rceil$. This would again provid a valid solution, and a better one that the previous, but this is only a $3$-approximation, not a $2$-approximation (proof left to you as an exercise).
$\endgroup$
3
  • $\begingroup$ Thank you for the detailed explanation. I have one question with the statement you said: "For an edge (u,v)∈E, either xu⩾1 or xv⩾2. That means that xu+xv2⩾1 (or equivalently 2xu+xv⩾2). There lies your first error, since you wrote xu+2xv⩾1 instead." Doesn't 2xu + xv ⩾2 would mean the multi-set can have atleast 2 u nodes and atleast 1 v node? My expression xu + 2xv meant atleast 1 u node and 2 v nodes. This might be a naive stupid question but I can't seem to get my head around. If you could please clarify this. $\endgroup$
    – ConScience
    Commented Jan 7, 2023 at 14:29
  • $\begingroup$ No, no, you are making the same mistake again: either $x_u \geqslant 1$ or $x_v\geqslant 2$, that means that $2x_u\geqslant 2$ or $x_v\geqslant 2$, so the sum of the two is $\geqslant 2$. Refer to the definition of $x_u$ and $x_v$: it is $x_v$ that needs to be greater that $2$, not $2x_v$, because $x_v$ is the number of times $v$ appears. $\endgroup$
    – Nathaniel
    Commented Jan 7, 2023 at 14:47
  • $\begingroup$ aah, now I get it! It has to be ⩾2 the sum. Perfect. Thank you so much. $\endgroup$
    – ConScience
    Commented Jan 7, 2023 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.