# To write an IP and relax it to LP for finding a multi-set in a graph

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.

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 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).
• 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. Commented Jan 7, 2023 at 14:29
• 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. Commented Jan 7, 2023 at 14:47
• aah, now I get it! It has to be ⩾2 the sum. Perfect. Thank you so much. Commented Jan 7, 2023 at 15:00