Affordable Access

Publisher Website

An approximation scheme for the two-stage, two-dimensional knapsack problem

Authors
Journal
Discrete Optimization
1572-5286
Publisher
Elsevier
Publication Date
Volume
7
Issue
3
Identifiers
DOI: 10.1016/j.disopt.2010.03.003
Keywords
  • Knapsack Problem
  • Shelf Packing
  • Polynomial Time Approximation Schemes

Abstract

Abstract We present an approximation scheme for the two-dimensional version of the knapsack problem which requires packing a maximum-area set of rectangles in a unit square bin, with the further restrictions that packing must be orthogonal without rotations and done in two stages. Achieving a solution which is close to the optimum modulo a small additive constant can be done by taking wide inspiration from an existing asymptotic approximation scheme for two-stage two-dimensional bin packing. On the other hand, getting rid of the additive constant to achieve a canonical approximation scheme appears to be widely nontrivial.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Approximation schemes for knapsack problems with s...

on Theoretical Computer Science Jan 01, 2006

On two-stage stochastic knapsack problems

on Discrete Applied Mathematics Jan 01, 2011

On the two-dimensional Knapsack Problem

on Operations Research Letters Jan 01, 2004
More articles like this..