Next: The future of the Up: Two peculiar statistics Previous: The oldest results

#### Distribution of performance ratios

Another interesting statistic is the number of problems that admit a specific performance ratio. The distribution of the performance ratios within the compendium is shown in Table 3 (note that the total number of problems in the table does not coincide with the total number of problems in the compendium since, for some problems, there are no good news at all). It is surprising that so many problems admit a 2-approximation algorithm: moreover, for most of them the algorithm is not known to be optimal.

Table 3: The distribution of performance ratios.
Performance ratio | Number of problems
FPTAS | 7
PTAS | 12
APX, | 10
APX, | 9
APX, <2 | 18
APX, 2 | 25
APX, >2 | 20
polylog | 38
poly | 26

Next: The future of the Up: Two peculiar statistics Previous: The oldest results