Does approximation ratio depend on the input size $n$?
Not all NP-hard problems admit constant factor approximation algorithms (in polynomial-time). One such well-known example is the problem of finding a maximum clique, which cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon &gt; 0$ unless P = NP (see Wikipedia, though this is also mentioned in the introduction of Williamson &amp; Shmoys).