| Article ID: | iaor19981307 |
| Country: | United States |
| Volume: | 41 |
| Issue: | 5 |
| Start Page Number: | 960 |
| End Page Number: | 981 |
| Publication Date: | May 1994 |
| Journal: | Journal of The Association for Computing Machinery |
| Authors: | Yannakakis M., Lund C. |
| Keywords: | optimization, combinatorial analysis |
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.