On the hardness of approximating minimization problems
Carsten Lund, Mihalis Yannakakis · Journal of the ACM · 1994
We prove results indicating that it is hard to compute efficiently good approximate solutions to the Graph Coloring, Set Covering and other related minimization problems.Specifically, there is an E > 0 such that Graph Coloring cannot be approximated with ratio n' unless P = NP.Set Covering cannot be approximated with ratio c log n for any c < l/4 unless NP is contained in DTIME(nP"Y'"~").Similar results follow for related problems such as Clique Cover, Fractional Chromatic Number, Dominating Set, and others.