[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [igraph] set cover

**From**: |
Raphael Clifford |

**Subject**: |
Re: [igraph] set cover |

**Date**: |
Tue, 24 Sep 2013 20:28:42 +0100 |

Thank you. I was looking for an exact (exponential time) solution.
Raphael
On 24 September 2013 20:12, Tamás Nepusz <address@hidden> 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*
>* address@hidden*
>* https://lists.nongnu.org/mailman/listinfo/igraph-help*