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 , no -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 -approximation algorithm for MINIMUM SET COVER: 25 years later it has
been proved that this algorithm is optimal [13]!