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$
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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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