Thank you. I was looking for an exact (exponential time) solution. Raphael
On 24 September 2013 20:12, Tamás Nepusz <[email protected]> wrote: >> I would like to solve an instance of minimum set cover. Is there some >> way to do this by formulating it the problem as a bipartite graph and >> using igraph? > > If you are looking for an exact solution, then the answer is probably no > (although I'm not 100% sure). However, there exists a greedy algorithm for > minimum set covers that achieves an approximation ratio of H(m) if there are > m items to be covered [1]. This greedy algorithm is fairly easy to implement: > > 1. Construct a bipartite graph where the first N vertices represent the sets > and the remaining M vertices represent the items to be covered. Connect an > item to a set if the item is in the set. > > 2. If there are no vertices to be covered, you are done. > > 3. Choose the set (i.e. the vertex among the first N vertices) with the > highest degree, add it to the cover and remove all its neighbors from the > graph. > > 4. Go to step 2. > > You can also combine the above technique with a local search using simulated > annealing or some other meta-heuristic, starting from the configuration given > by the greedy algorithm. > > [1] http://www.jstor.org/stable/3689577 > > -- > T. > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
