论文标题
$ 4/3 \ CDOT OPT+2/3 $近似，用于大型两杆图表包装问题
A $4/3\cdot OPT+2/3$ approximation for big two-bar charts packing problem
论文作者
论文摘要
两杆图表包装问题是将$ n $两杆图表（2-BC）打包成最少数量的单位容量箱。这个问题概括了强烈的NP坚硬垃圾箱包装问题。我们证明，即使每个2-BC至少高于1/2，问题仍然很强烈。接下来，我们考虑每个2-BC的第一个（或第二个）栏高于1/2的情况，并表明$ O（n^2）$ - 时间贪婪算法和2-BCS的初步词典订购2-BCS构造长度的封装最多$ opt $ opt+1 $，而$ opt $ opt $是最佳的。最终，该结果使我们能够提出$ O（n^{2.5}）$ - 时间算法，该算法最多构建长度的填料，最多为$ 4/3 \ cdot opt+2/3 $，对于每个2-BC至少一个bar的bar至少一个bar高于1/2。
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.
