A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set

A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set

0.00 Avg rating0 Votes
Article ID: iaor1997984
Country: France
Volume: 28
Issue: 4
Start Page Number: 426
End Page Number: 462
Publication Date: Oct 1994
Journal: Recherche Oprationnelle/Operations Research
Authors:
Keywords: sets
Abstract:

Let equ1 be a universal constant denoting the approximation ratio of a hypothetical polynomial time approximation algorithm for the instances of the independent set problem with equ2, where G is a graph of order n and stability number equ3. Let finally suppose the existence of a (universally) constant-ratio-polynomial-time-approximation-algorithm for set covering problem. Then, there exists a polynomial time approximation algorithm for vertex covering problem with a ratio bounded above by max equ4 for a equ5 arbitrarily small.

Reviews

Required fields are marked *. Your email address will not be published.