  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.

Computational Geometry;Optimization and Control