0
$\begingroup$

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I am considering each element as a vertex. Now I will find minimum edge cover of this graph(hyperGraph). Is this the right way to do?

$\endgroup$
  • $\begingroup$ How do you turn a set with 3 elements to an edge, which is incident to only 2 vertices? $\endgroup$ – xskxzr Mar 2 at 5:20
  • $\begingroup$ that is hyper edge. $\endgroup$ – Manoharsinh Rana Mar 2 at 9:34
0
$\begingroup$

Yes. This is a right and possible way to go.

One can also consider the formulation of the set cover problem as an Integer Program, using the LP relaxation of such program you can obtain what is referred as $f$-approximation. Details and analysis can be found in most standard books on approximation algorithms.

$\endgroup$
  • $\begingroup$ is minimum edge cover for hypergraph polynomial time solvable? $\endgroup$ – Manoharsinh Rana Jan 31 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.