  In this work, we study the square min-sum bin packing problem (SMSBPP), where
a list of square items has to be packed into indexed square bins of dimensions
$1 \times 1$ with no overlap between the areas of the items. The bins are
indexed and the cost of packing each item is equal to the index of the bin in
which it is placed in. The objective is to minimize the total cost of packing
all items, which is equivalent to minimizing the average cost of items. The
problem has applications in minimizing the average time of logistic operations
such as cutting stock and delivery of products. We prove that classic
algorithms for two-dimensional bin packing that order items in non-increasing
order of size, such as Next Fit Decreasing Height or Any Fit Decreasing Height
heuristics, can have an arbitrarily bad performance for SMSBPP. We, then,
present a $\frac{53}{22}$-approximation and a PTAS for the problem.
