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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Why not try to prove it? This is how we verify conjectures in mathematics. $\endgroup$
    – Yuval Filmus
    Aug 15, 2019 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, 2019 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, 2019 at 9:25

0

Reset to default

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.