On Two Dimensional Orthogonal Knapsack Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 $\frac65+ε$ approximation algorithm.

Keywords

Data Structures and Algorithms, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/212253

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0803.4260
 http://arxiv.org/abs/0803.4260

Collections

arXiv