next up previous
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, $\leq 4/3$ 10
APX, $\leq 3/2$ 9
APX, <2 18
APX, 2 25
APX, >2 20
polylog 38
poly 26


next up previous
Next: The future of the Up: Two peculiar statistics Previous: The oldest results
Viggo Kann
1998-10-31