A 3/2–approximation for big two-bar charts packing
share
We consider a Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generalization of the Bin Packing Problem (BPP). Earlier, we proposed an O(n^2)-time algorithm that constructs the packing which length at most 2· OPT+1, where OPT is the minimum length of the packing of n 2-BCs. In this paper, we propose an O(n^4)-time 3/2-approximate algorithm when each BC has at least one bar greater than 1/2.
READ FULL TEXT