Recently, I've encountered the following problem:

Given a collection of sets $S_1 \dots S_n$ of elements $e_1 \dots e_k$ with element $e_k$ denoted privileged, and a $k-1$-vector $r$, choose at most $m$ of the $n$ sets to maximize the number of times the privileged element $e_k$ occurs in the multiset union of the chosen sets, subject to that each other element $e_i$ must occur at least $r_i$ times in that union. Each set in the collection can be chosen at most once, but the collection may contain duplicate sets.

This can be reduced to solving a constrained set multicover problem (CSMP) with various values of $r_k$ to determine the maximum possible value that keeps the minimal number of sets at or below $m$.

In my context, taking a fractional amount of a set is allowed (e.g. taking 0.1 of $S_1$ counts as contributing 0.1 towards the capacity constraint of every element that's in $S_1$, and towards the maximum $m$ constraint). The fractional version of either the privileged cover problem or the CSMP can be cast as a linear programming problem and thus solved in polynomial time.

Now here's my problem: in my context, $n$ can be on the order of millions, while $m$ is on the order of hundreds. So while linear programming works and is polytime, it would be very slow in practice. I've been trying to find out how either my problem or the CSMP can be solved more quickly, but I've not had any luck. All I can find is information about how to use duality to approximate the integral version of the CSMP, which doesn't seem to be applicable here.

What is known about the complexity of solving the fractional CSMP or set covering problems in general? Are any faster algorithms than LP known to exist for either the fractional CSMP or my privileged cover problem? And if not, what kind of theory is applicable to determining whether such algorithms exist?

  • $\begingroup$ If we ignore $m$, the only way that your problem is special compared to a generic linear programming instance is that you are promised that each coefficient in each linear inequality is either 0 or 1. So, if can we solve LP faster if we know that all coefficients are 0 or 1, that would help with your problem. $\endgroup$ – D.W. Feb 5 at 3:32

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.