Next: Improving the compendium
Up: Introduction
Previous: Completeness in approximation classes
  Index
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: Improving the compendium
Up: Introduction
Previous: Completeness in approximation classes
  Index
Viggo Kann
2000-03-20