zbMATH — the first resource for mathematics

Approximation algorithms for bin-packing - an updated survey. (English) Zbl 0558.68062
Algorithm design for computer system design, CISM Courses Lect. 284, 49-106 (1984).
[For the entire collection see Zbl 0547.00037.]
This paper updates a survey [M. R. Garey and D. S. Johnson, Analysis and design of algorithms in comb. opt., CISM Courses and Lect. 266, 147-172 (1981; Zbl 0484.68028)] written about 3 years ago. All of the results mentioned there are covered here as well. However, as a major justification for this second edition we shall be presenting many new results, some of which represent important advances. As a measure of the impressive amount of research in just 3 years, the present reference list more than doubles the list in the mentioned paper.
Reviewer: Reviewer (Berlin)

68R99 Discrete mathematics in relation to computer science
90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
68-02 Research exposition (monographs, survey articles) pertaining to computer science
00A15 Bibliographies for mathematics in general
05B40 Combinatorial aspects of packing and covering
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming