Loading...
Please wait, while we are loading the content...
Similar Documents
On two dimensional orthogonal knapsack problem (2008).
| Content Provider | CiteSeerX |
|---|---|
| Author | Han, Xin Iwama, Kazuo Zhang, Guochuan |
| Abstract | In this paper, we study the following knapsack problem: Given a list of squares with profits, we are requested to pack a sublist of them into a rectangular bin (not a unit square bin) to make profits in the bin as large as possible. We first observe there is a Polynomial Time Approximation Scheme (PTAS) for the problem of packing weighted squares into rectangular bins with large resources, then apply the PTAS to the problem of packing squares with profits into a rectangular bin and get a 6 5 + ǫ approximation algorithm. |
| File Format | |
| Publisher Date | 2008-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dimensional Orthogonal Knapsack Problem Rectangular Bin Large Resource Following Knapsack Problem Unit Square Bin Polynomial Time Approximation Scheme Approximation Algorithm Weighted Square |
| Content Type | Text |
