论文标题
3/2 - 大型两杆图表包装的Approximation
A 3/2--approximation for big two-bar charts packing
论文作者
论文摘要
我们考虑一个两条杆图表包装问题（2-BCPP），其中有必要在最小长度的单位高度条中包装两条杆图（2-BC）。问题是对垃圾箱包装问题（BPP）的概括。此前，我们提出了一个$ O（n^2）$ - 时间算法，该算法构建了包装最多最多2 \ cdot opt+1 $，其中$ opt $是$ n $ 2-bcs的最小包装长度。在本文中，我们提出了一个$ o（n^4）$ - 时间3/2-当每个BC的算法至少一个大于1/2时。
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\cdot 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.
