The oldest results

The oldest result contained in the compendium is a 4/3-approximation algorithm for MINIMUM EDGE COLORING due to [14]. Actually, this algorithm is optimal since in [8] it is shown that, for any $\varepsilon >0$, no $(4/3-\varepsilon )$-approximation algorithm exists for this problem. It is worth pointing out that in neither of the above two references the notion of approximation algorithm is explicitly used.

The second oldest result, instead, is due to [9] which is widely considered the starting point of the theory of approximation algorithm (indeed, the compendium contains four results due to this paper). In particular, the above reference contains a $(1+\ln n)$-approximation algorithm for MINIMUM SET COVER: 25 years later it has been proved that this algorithm is optimal [13]!