Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
