[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] set cover
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] set cover |
Date: |
Tue, 24 Sep 2013 21:12:24 +0200 |
> 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.