# An LP with two covering constraints - how to round

I came across an LP with two covering problems, and I wonder how to find a good approximation. For the relevant part of the LP: We have a set $$E$$ , for each $$e\in E$$ we have a corresponding set $$Y_{e}\subseteq E$$. We have some set fixed size sets $$U_{k}\subseteq E$$ and we look at this LP $$\min\,\sum_{e\in E}x_{e}c(e)+\sum_{f\in E}y_{f}c(y)$$ $$s.t\,\sum_{e\in U_{k}}x_{e}\geq1\,\forall U_{k}$$ $$\sum_{e\in Y_{f}}y_{f}\geq x_{e}$$ $$x_{e},y_{f}\in[0,1]$$

If I had just the first constraint this would be an instance of Set-Cover and we would have a $$O(\lg n)$$ approximation, the problem is that we also have to cover each $$e$$ with a set $$Y_{f}$$ s.t $$e\in Y_{f}$$.

My question: How can I find a low cost of $$y_{f}$$ after I round the $$x_{e}$$ variables.

I have three ideas, two of which I can analyze.

First Idea: I'm looking at randomized rounding with the following

1. Round $$x_{e}^{*}$$ to $$1$$ with probability $$x_{e}^{*}$$
2. For each $$x_{e}^{*}$$ that was rounded to $$1$$ round an element $$f\in E$$ s.t $$e\in Y_{f}$$ and $$y_{f}^{*}$$ is maximal
3. Repeat the first two steps independently $$c\ln(n)$$ times

Consider $$f$$ s.t $$y_{f}^{*}$$ was rounded to $$1$$, this means there is $$e\in E$$ with $$e\in Y_{f}$$ s.t $$y_{f}^{*}\geq\frac{x_{e}^{*}}{|E|}$$. We rounded from $$y_{f}^{*}$$ (which lies in $$[0,1]$$) to $$1$$ so we incur a factor of $$\frac{1}{y_{f}^{*}}\leq|E|\cdot x_{e}^{*}\leq|E|$$ to the cost. We get a $$O(\log n)$$ bound for the first part of the sum and $$O(|E|)$$ for the second part of the sum. In my case $$|E|=O(n^{2})$$ and we repeat $$c\ln(n)$$so this is an $$O(n^{2}\ln(n))$$ approximation.

Second Idea: in the second step round $$y_{f}^{*}$$ to $$1$$ with probability $$y_{f}^{*}$$, and in the third step repeat $$c\cdot n^{2}\ln(n)$$ times. Since $$\sum_{x\in Y_{f}}y_{f}^{*}\geq x_{e}^{*}$$ then the event that $$x_{e}^{*}$$ was rounded to $$1$$ and that there is $$y_{f}^{*}$$ that was rounded to $$1$$ s.t $$e\in Y_{f}$$ is $$(\sum_{x\in Y_{f}}y_{f}^{*}\cdot x_{e}^{*})\geq x_{e}^{*}$$. If we plug $$x_{e}^{*}$$ into the set cover analysis we get that the probability that we have a covering of $$x_{e}$$ that are covered by $$y_{e}$$ as $$e^{-c\cdot n^{2}\ln(n)\sum x_{e}^{*}}$$. We know that $$\sum_{x\in U}x_{e}\geq1$$ and we want a bound for $$\sum_{x\in U}x_{e}^{2}\geq1$$ which can be given by Cauchy\textendash Schwarz inequality as $$(\sum_{x\in U}x_{e})^{2}\leq|U|\sum_{x\in U}x_{e}^{2}$$. Since $$|U|\leq|E|=O(n^{2})$$ If we plug this back we get a high probability of the covering - but now the approximation ,which is the number of repetitions , is $$O(n^{2}\ln(n))$$ which is the same result.

Third Idea: Create an instance of set cover after the first step and final an optimal covering of the elements $$e$$ which we rounded $$x_{e}^{*}$$ to $$1$$ - my problem is I can't compare to the cost of the objective of the LP we start with but rather just to the goal of LP of the set cover instance we define.

I would appreciate more ideas or corrections, I hope to reach a ratio of $$O(\ln^{k}n)$$ for some constant $$k$$.