Approximation thresholds for combinatorial optimization problems
<|reference_start|>Approximation thresholds for combinatorial optimization problems: An NP-hard combinatorial optimization problem $\Pi$ is said to have an {\em approximation threshold} if there is some $t$ such that the optimal value of $\Pi$ can be approximated in polynomial time within a ratio of $t$, and it is NP-hard to approximate it within a ratio better than $t$. We survey some of the known approximation threshold results, and discuss the pattern that emerges from the known results.<|reference_end|>
@article{feige2003approximation,
    title={Approximation thresholds for combinatorial optimization problems},
    author={Uriel Feige},
    journal={Proceedings of the ICM, Beijing 2002, vol. 3, 649--658},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0304039},
    primaryClass={cs.CC}
}