5
$\begingroup$

Does anyone know of any tools that solve the approximate minimum set cover problem?

I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about more sophisticated algorithms/heuristic that do better on many problems in practice. (e.g., Algorithms for the Set Covering Problem by Caprara et al.) Are there any implementations generally available? Any tools that others can use to find approximately optimal solutions, for large problem instances? I'd prefer to use an existing tool, rather than try to understand and implement these sophisticated algorithms myself.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I would welcome feedback about whether this question is suitable, on-topic, and a good fit for this site. (For instance, should I ask on CS.SE instead?) $\endgroup$ – D.W. Sep 17 '12 at 7:37
  • $\begingroup$ see about finding code for algorithms. imho there are particular algorithms that have a TCS flavor with set covering definitely affirmative... try also "application-of-theory" tag $\endgroup$ – vzn Sep 20 '12 at 0:46
3
$\begingroup$

sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider Espresso, a logic minimizer. its open source and mainly written in C. it has a built in [exact] and also heuristic set cover as a subroutine after generating prime implicants for SAT. the exact covering is chosen with a command line switch.

ie it implements the Quine-McCluskey method where set cover is part of the final optimization. there is some research on an improved exact set cover (also called the "minimum canonical cover") by McGeer et al called Espresso Signature which was implemented but may be more difficult to obtain source code.

note the set cover algorithms are apparently decoupled in the code but possibly not decoupled in the interface. ie it might require a little bit of "wrapper" coding to provide a direct interface to the set cover subroutines. another possibility is using monotone formula inputs in which there are no "derived" prime implicants other than those supplied as input in which the entire logic minimization reduces to set cover only.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ note the optimum cover takes exponential time in worst case and the heuristics run in less time but dont guarantee the optimum which may be "good enough" for many applications $\endgroup$ – vzn Sep 20 '12 at 22:57

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.