Jansen, Klaus and Solis-Oba, R. (2012) PACKING SQUARES WITH PROFITS. Siam Journal on Discrete Mathematics, 26 (1). pp. 263-279.

Full text not available from this repository.

Abstract

We study the following square packing problem: Given a set Q of squares with positive profits, the goal is to pack a subset of Q into a rectangular bin R so that the total profit of the squares packed in R is maximized. Squares must be packed so that their sides are parallel to those of R. We present a polynomial time approximation scheme for the problem, which for any value epsilon > 0 finds and packs a subset Q' subset of Q of profit at least (1 - epsilon)OPT, where OPT is the profit of an optimum solution.

Document Type:	Article
Additional Information:	Univ Kiel, Inst Informat, Kiel, Germany. Univ Western Ontario, Dept Comp Sci, London, ON, Canada. Jansen, K (reprint author), Univ Kiel, Inst Informat, Kiel, Germany. kj@informatik.uni-kiel.de; solis@csd.uwo.ca
Keywords:	polynomial time approximation scheme square packing 2-dimensional packing resource augmentation approximation algorithms
Research affiliation:	OceanRep > The Future Ocean - Cluster of Excellence
Projects:	Future Ocean
Date Deposited:	14 May 2014 10:00
Last Modified:	14 May 2014 10:00
URI:	https://oceanrep.geomar.de/id/eprint/24051

Actions (login required)

View Item