CODEWITHSUNDEEP
algorithmbacktracking
HMdeveloper
HMdeveloper

Reputation: 2884

looking for better bound to stop earlier in set cover

I am trying to solve set cover problem in a way that vertex cover is solved

Input: we have a base set X and collection C of subsets of X, so that each element in C is a subset of X

Output: the size of the smallest set F from set in C in a way that the union of all elements of F results in X

I know how to solve this but I am looking for a heuristic to stop going further in the tree earlier. For example Now I remove each element from C and do a recursive call and I check for stopping point in this way: if(bestsofar <= F.length+1) stop

but I know that there would be better heuristic because for example in vertex cover I can check like this : if K+1 >best stop; which k is the number of added vertice in the result to cover edges but the better approach is if K+ number Edges/maxdeg >=best stop which is much better.

I want the same thing for set-cover .

does anyone have any idea?

Upvotes: 0

Views: 52

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

From a theoretical perspective, what your heuristic for vertex cover is doing is constructing a feasible solution to the dual of the relaxed linear program for vertex cover. The same can be done for set cover. If for whatever reason you don't want to use the simplex method to find the optimal dual solution, then there are a variety of approximations available. You could use K plus the number of items divided by maximum number of items in a set, which generalizes your heuristic for vertex cover. You also could use a greedy algorithm to find a packing, by which I mean the following. For vertex cover, this would be a set of edges with no endpoints in common (i.e., a matching). Every cover contains at least one endpoint of each of the edges in the packing. For set cover, this would be a collection of items such that no set contains more than one item of the collection.

Upvotes: 1

Related Questions