5
$\begingroup$

I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be many more others that can be solved by set cover.

$\endgroup$
4
$\begingroup$

Set-cover heuristics are used in random testing ("fuzz testing") of programs. Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes. We'd like to do this over and over again. If we do this naively, it will be less effective than it could be: typically many test cases cover basically the same code paths, but a small minority of test cases cover unusual code paths that would be interesting to test more intensively.

So, here's one solution that is used in industry. We use a coverage measurement tool to instrument the program and record which lines of code are covered by each of the million test cases. Then, we choose a small subset $S$ of those million test cases that has maximal coverage: every line of code covered by one of the million test cases will be covered by some test case in $S$. $S$ is called a reduced test suite. We then apply random mutation & testing to the reduced test suite $S$. Empirically, this seems to make random testing more effective. The smaller $S$ is, the more effective and efficient testing becomes.

So, how do we choose a reduced test suite $S$ that is as small as possible, while still achieving maximal coverage? Answer: that's a set cover problem, so we use standard heuristics/approximation algorithms for the set cover problem. The standard greedy approximation algorithm is typically used for this purpose.

$\endgroup$
4
$\begingroup$

Not sure if this is a real-world problem – solving sudokus can be reduced to an exact cover problem (note that exact cover is related to set cover, but not the same). You can find similar explanations here. Some fast solvers directly use Knuth's dancing links to solve sudokus, which is usually much faster than naive backtracking. However, the fastest solvers to date actually don't reduce sudoku solving to exact cover. They apply plain backtracking combined with advanced searching heuristics and careful code optimization.

$\endgroup$
2
$\begingroup$

By far the most relevant, large size, important application of set covering is in personnel shift planning (mainly in large airline companies). There, elements to be covered are the single shifts (or single flights), and sets are legal combinations of work/no work schedules. These easily go to millions or even billions of variables, as the number of combination is huge.

$\endgroup$
  • $\begingroup$ Hi, Fabio and welcome to the site! I edited your post to remove your signature, since posts here are automatically "signed" and the link to your group homepage wasn't directly relevant to your answer. But please do feel free to add that link to your profile page -- it would be completely appropriate there! $\endgroup$ – David Richerby Jan 8 '18 at 18:02
  • $\begingroup$ Could you please explain why this is a set cover problem? There must be one base set that needs to be covered, e.g. the set of all flights. But what are then the subsets that can be used for coverage? Probably there are some sort of local work/no work schedules, and each such work schedule determines a set of flights that is being covered? Then a number of such local work/no work schedules must be selected, such that each flight is covered exactly once, yielding a global work/no work schedule? $\endgroup$ – tillmo Jan 15 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.