SOME APPROXIMATION RESULTS IN THE FRAME O F A NEW POLYNOMIAL-APPROXIMATION THEORY

In this Note we give some results in the context of a new polynomial a pproximation theory which we have introduced in an earlier Note. We pr opose a polynomial time algorithm for minimum set covering with an app roximation ratio depending on the maximum set cardinality, a constant ratio polynomial time approximation algorithm for the minimum vertex c oloring problem, an asymptotically constant ratio polynomial time appr oximation algorithm for bin packing, and finally an approximation rati o preserving reduction between minimum vertex covering by cliques and minimum edge covering by cliques.