点击次数：

论文类型：会议论文

发表时间：2011-05-28

收录刊物：EI、CPCI-S

卷号：6681

页面范围：176-184

摘要：In this paper, we study a two-dimensional knapsack problem: packing squares as many as possible into a unit square. Our results are the following:
   (i) first, we propose an algorithm called IHS(Increasing Height Shelf), and prove that the packing is optimal if there are at most 5 squares packed in an optimal packing, and this upper bound 5 is sharp;
   (ii) secondly, if all the items have size(side length) at most 1/k, where k >= 1 is a constant number, we propose a simple algorithm with an approximation ratio k2+3k+2/k2 in time O(n log n).
   (iii) finally, we give a PTAS for the general case, and our algorithm is much simpler than the previous approach[16].