THE APPROXIMABILITY BEHAVIOR OF SOME COMBINATORIAL PROBLEMS WITH RESPECT TO THE APPROXIMABILITY OF A CLASS OF MAXIMUM INDEPENDENT SET PROBLEMS

We prove that the existence of a polynomial time rho-approximation alg orithm (where rho < 1 is a fixed constant) for a class of independent set problems, leads to a polynomial time approximation algorithm with approximation ratio strictly smaller than 2 for vertex covering, while the non-existence cf such an algorithm induces a lower bound on the r atio of every polynomial time approximation algorithm for vertex cover ing. We also prove a similar result for a (maximization) convex progra mming problem including quadratic programming as subproblem.