0
$\begingroup$

In the Set Cover problem we need to cover each element at least once. I'm considering the case where I want each element to be covered at least $k$ times with constant $k$.

I consider the classic LP for the problem and randomized rounding. Is it indeed the case that the modification of the LP from $\geq 1$ to $\geq k$ in the covering constraint and with the same rounding (up to the number of repetitions) works well for this variant as well?

It looks like it, but I'm not sure if I'm missing anything.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Why not try to prove it? This is how we verify conjectures in mathematics. $\endgroup$ – Yuval Filmus Aug 15 '19 at 7:11
  • $\begingroup$ @YuvalFilmus, It's the same proof, I just wanted a verification that I wasn't missing anything $\endgroup$ – Belgi Aug 15 '19 at 7:26
  • $\begingroup$ If your proof works, then the statement is correct. There's no need for independent verification. $\endgroup$ – Yuval Filmus Aug 15 '19 at 9:25

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.