An Improved Approximation for Packing Big Two-Bar Charts
share
Recently, we presented a new 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 and 2-D Vector Packing Problem. Earlier, we have proposed several polynomial approximation algorithms. In particular, when each 2-BC has at least one bar of height more than 1/2, we have proposed a 3/2–approximation polynomial algorithm. This paper proposes an O(n^3)–time 16/11–approximation algorithm for packing 2-BCs when at least one bar of each BC has a height not less than 1/2 and an O(n^2.5)–time 5/4–approximation algorithm for packing non-increasing or non-decreasing 2-BCs when each 2-BC has at least one bar which height is more than 1/2, where n is the number of 2-BCs.
READ FULL TEXT