科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1, ... , C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4+epsilon)-approximation algorithm when the bin is a square. We also present (3+epsilon)-approximation algorithms for two special cases of this problem.
- 出版日期2013-10
