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$.


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.