Re: [igraph] set cover

[Raphael Clifford]

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