next up previous index
Next: Improving the compendium Up: Introduction Previous: Completeness in approximation classes   Index

A list of NPO problems

The list contains more than 200 entries. A typical entry consists of eight parts: the first four parts are mandatory while the last four parts are optional.

1.
The problem name that also specifies the goal of the problem.

2.
The definition of the instances of the problem.

3.
The definition of the feasible solutions of the problem.

4.
The definition of the measure of a feasible solution.

5.
A `good news' part that contains the best approximation result for the problem.

6.
A `bad news' part that contains the worst approximation negative result for the problem.

7.
A section of additional comments.

8.
A reference to the `closest' problem appearing in the list published in [182].

Observe that the problem definitions that appear in the list follow the notation of [182] while, in some cases, the definitions given in the previous chapters correspond to the most widely used in the literature: in any case, the differences between the two definitions are just a matter of notations.

The list is organized according to subject matter as done in [182]. In particular the entries are divided into the following twelve categories:

GT
Graph theory
ND
Network design
SP
Sets and partitions
SR
Storage and retrieval
SS
Sequencing and scheduling
MP
Mathematical programming
AN
Algebra and number theory
GP
Games and puzzles
LO
Logic
AL
Automata and language theory
PO
Program optimization
MS
Miscellaneous

We have ignored problems with too obscure definitions and problems for which the membership in NP was not guaranteed. Furthermore we have only included results for ordinary polynomial time approximation algorithms, not for e.g. bicriteria approximation algorithms and on-line algorithms.


next up previous index
Next: Improving the compendium Up: Introduction Previous: Completeness in approximation classes   Index
Viggo Kann
2000-03-20