0
$\begingroup$

For TSP there are well known heuristic and approximation solutions which run in low-polynomial time, like Christofides / 2-OPT and so on.

I need a practical, fast algorithm, ideally sub-quadratic complexity, to solve the minimum weighted set cover problem (which is NP hard). It solves subproblems in a genetic algorithm so needs to be fast rather than optimal. Are there any standard algorithms used to solve this?

$\endgroup$
1
$\begingroup$

One possibility is to use the standard greedy algorithm. It can be adapted to weighted set cover by counting the total weight of previously uncovered elements that will be covered by adding a particular set, instead of counting the number of such elements. This is standard and covered in standard textbooks and resources. Another option is to use linear programming or integer linear programming. A little research on set cover approximation algorithms will find much more that is written on the subject. In the future, I suggest doing more research before asking here.

$\endgroup$

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.