Approximation algorithms for the Square Min-Sum Bin Packing Problem

Abstract In this work, we study the Square Min-Sum Bin Packing Problem (SMSBPP), where a list of n square items has to be packed into square bins of dimensions $$1 \times 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>×</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> with no overlap between the areas of the items. The bins are indexed (starting at one) and the cost of packing each item is equal to the index of the bin in which it is placed. 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 an algorithm with an approximation ratio of $$\sqrt{205}-12+\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msqrt> <mml:mn>205</mml:mn> </mml:msqrt> <mml:mo>-</mml:mo> <mml:mn>12</mml:mn> <mml:mo>+</mml:mo> <mml:mi>δ</mml:mi> </mml:mrow> </mml:math> ( $$\approx 2.3178+\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>≈</mml:mo> <mml:mn>2.3178</mml:mn> <mml:mo>+</mml:mo> <mml:mi>δ</mml:mi> </mml:mrow> </mml:math> ), for any $$\delta &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , and running time $$O(n \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Finally, we also present a PTAS for the problem.