点击次数：

论文类型：期刊论文

发表时间：2013-10-14

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：508

页面范围：35-40

ISSN号：0304-3975

摘要：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) we propose an algorithm called IHS (Increasing Height Shelf), and prove that the packing is optimal if in an optimal packing there are at most 5 squares, and this upper bound is sharp;
   (ii) if all the squares have side length at most 1/k., we propose a simple and fast algorithm with an approximation ratio k(2)-3k+2/k(2) in time O(n log n);
   (iii) we give an EPTAS for the problem, where the previous result in Jansen and Solis-Oba (2008)[16] is a PTAS, not an EPTAS. However our approach does not work on the previous model of Jansen and Solis-Oba (2008) [16], where each square has an arbitrary weight. (C) 2012 Elsevier B.V. All rights reserved.