ON THE HARDNESS OF APPROXIMATING MINIMIZATION PROBLEMS

We prove results indicating that it is hard to compute efficiently goo d approximate solutions to the Graph Coloring, Set Covering and other related minimization problems. Specifically, there is an epsilon > 0 s uch that Graph Coloring cannot be approximated with ratio n(epsilon) u nless P = NP. Set Covering cannot be approximated with ratio c log n f or any c < 1/4 unless NP is contained in DTIME(n(poly log n)). Similar results follow for related problems such as Clique Cover, Fractional Chromatic Number, Dominating Set, and others.