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.
No takes yet. Share an insight, caveat, or question.
Lund et al. (1994) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: