CRIS Current Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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.
| Titolo: | An Approximation Scheme for Two-Stage, Two- Dimensional Knapsack | |
| Autore/i: | CAPRARA, ALBERTO; LODI, ANDREA; MONACI, MICHELE | |
| Autore/i Unibo: | ||
| Anno: | 2010 | |
| Rivista: | ||
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.disopt.2010.03.003 | |
| 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. | |
| Data prodotto definitivo in UGOV: | 2011-02-24 22:55:07 | |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11585/86349
Copyright © 2021