We address the 2-dimensional Knapsack Problem (2KP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the 1-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their effectiveness.

On the 2-Dimensional Knapsack Problem / CAPRARA A.; M. MONACI. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 32:(2004), pp. 5-14. [10.1016/S0167-6377(03)00057-9]

On the 2-Dimensional Knapsack Problem

MONACI, MICHELE
2004

Abstract

We address the 2-dimensional Knapsack Problem (2KP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the 1-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their effectiveness.
2004
On the 2-Dimensional Knapsack Problem / CAPRARA A.; M. MONACI. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 32:(2004), pp. 5-14. [10.1016/S0167-6377(03)00057-9]
CAPRARA A.; M. MONACI
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/1109
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 96
  • ???jsp.display-item.citation.isi??? 79
social impact