In the set multicover problem we are given a set $N$ of $n$ elements and a set $S$ of $m$ subsets of $N$. Additionally, each element has a coverage requirement (the number of times it has to be covered) and each set has a weight. The question is to cover $N$ with the minimum weight subsets from $S$. I'm aware of the approximation algorithm for this problem using (Rajagopalan & Vazirani) .

But I am interested in finding an algorithm for this problem that uses the randomized rounding and study its approximation factor.

Thanks in advance!

  • $\begingroup$ Do you have in mind the variant of the problem where you can use each set as many times as desired (paying its cost each time)? For that case see algnotes.info/on/obliv/greedy/set-multicover-unconstrained . $\endgroup$ – Neal Young Jan 9 at 21:06
  • $\begingroup$ I am looking for the classical constrained multicover approximation algorithm. But until now I could find just examples using dual fitting and I couldn't find examples that uses randomized rounding with the proof of the approximation factor. $\endgroup$ – user2404626 Jan 10 at 15:04
  • $\begingroup$ There are some randomized-rounding approaches for the more general problem of solving covering integer programs with multiplicity constraints. You can start here and work backwards through the references (see papers by Harris et al and Kolliopoulos et al.) I don't know of any rounding scheme that is as clean and simple as the standard set cover rounding schemes. I'd be interested to know if there is something. $\endgroup$ – Neal Young Jan 10 at 18:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.