Hardest problems to approximate Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon &gt;0$. Are there any other problems that are known to be equally hard to approximate? I'm particularly interested in unweighted problems.
A similar hardness result is known for the inapproximability of chromatic number [1]. Independent set is hard to approximate as well, since it is $\mathsf{MAX\text{-}CLIQUE}$ on the complement graph. Some problems that are easier to approximate include vertex cover, (connected) dominating set, feedback vertex set, TSP and Steiner tree.



[1] Zuckerman, David. "Linear degree extractors and the inapproximability of max clique and chromatic number." Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. ACM, 2006.