zbMATH — the first resource for mathematics

Computational complexity: the problem of approximation. (English) Zbl 0616.68039
Algebra, combinatorics and logic in computer science, Colloq. Györ/Hung. 1983, Vol 1, Colloq. Math. Soc. János Bolyai 42, 51-62 (1986).
[For the entire collection see Zbl 0593.00024.]
An outline of combinatorial optimization problems from the NP- completeness theory point of view is worked out. The importance of approximation algorithms is also stressed, and some results concerning the performance evaluation function, bin packing, and network flow equilibrium problems are presented.

68Q25 Analysis of algorithms and problem complexity
90C27 Combinatorial optimization
90B10 Deterministic network models in operations research