Two-Bar Charts Packing Problem is to pack $n$ two-bar charts (2-BCs) in a minimal number of unit-capacity bins. This problem generalizes the strongly NP-hard Bin Packing Problem. We prove that the problem remains strongly NP-hard even if each 2-BC has at least one bar higher than 1/2. Next we consider the case when the first (or second) bar of each 2-BC is higher than 1/2 and show that the $O(n^2)$-time greedy algorithm with preliminary lexicographic ordering of 2-BCs constructs a packing of length at most $OPT+1$, where $OPT$ is optimum. Eventually, this result allowed us to present an $O(n^{2.5})$-time algorithm that constructs a packing of length at most $4/3\cdot OPT+2/3$ for the NP-hard case when each 2-BC has at least one bar higher than 1/2.

翻译：两巴图表包装问题在于将两巴图(2-BCs)包装在最小数量的单位容量箱中。 这个问题概括了强烈的NP- 硬本包装问题。 我们证明问题仍然是强烈的NP- 硬的。 即使每2- BCs至少有一巴高于1/2。 接下来我们考虑的是,每2- BC的第一个(或第二)巴高于1/2的情况, 并表明$O(n%2) $- time 贪婪算法, 初步地订购了2- BCs, 其包装的长度最多为$OPT+1美元, 其中美元是最佳的。 最终, 这一结果使我们能够提出一个美元( ⁇ 2.5}) 的时间算法, 其包装长度最多为 4/3\cdd OFM+2/3美元, 当每2- BCs至少有一巴高于1/2时。