Bin packing with general cost structures

packing, called "bin packing with general cost structures" (GCBP)
and design an asymptotic fully polynomial time approximation
scheme (AFPTAS) for this problem. In the classic bin packing
problem, a set of one-dimensional items is to be assigned to
subsets of total size at most 1, that is, to be packed into unit
sized bins. However, in GCBP, the cost of a bin is not 1 as in
classic bin packing, but it is a non-decreasing and concave
function of the number of items packed in it, where the cost of an
empty bin is zero. The construction of the AFPTAS requires novel
techniques for dealing with small items, which are developed in
this work. In addition, we develop a fast approximation algorithm
which acts identically for all non-decreasing and concave
functions, and has an asymptotic approximation ratio of 1.5 for
all functions simultaneously.