We consider a storage allocation problem with inclusion-free item time periods. It is given a set of items to be stored. Each item is characterize by an arrival time, a departure time and a size. Two items to be stored in the same time periods are allocate in different positions. The objective of the problem is to minimize the size of the allocation space. We prove that this problem is NP-hard, and give a linear time 2-approximation algorithm, based on a partition of the item set. The bound is shown to be tight.

Confessore, G., Dell'Olmo, P., Giordani, S. (1999). A linear time approximation algorithm for a storage allocation problem. In SYSTEMS MODELLING AND OPTIMIZATION (pp.253-260). BOCA RATON : CRC PRESS-TAYLOR & FRANCIS GROUP.

A linear time approximation algorithm for a storage allocation problem

GIORDANI, STEFANO
1999-01-01

Abstract

We consider a storage allocation problem with inclusion-free item time periods. It is given a set of items to be stored. Each item is characterize by an arrival time, a departure time and a size. Two items to be stored in the same time periods are allocate in different positions. The objective of the problem is to minimize the size of the allocation space. We prove that this problem is NP-hard, and give a linear time 2-approximation algorithm, based on a partition of the item set. The bound is shown to be tight.
18th IFIP TC7 Conference on Systems Modelling and Optimization
DETROIT, MI
JUL 22-25, 1997
Int Federat Informat Processing, Oakland Univ Sch Engn & Comp Sci
Rilevanza internazionale
contributo
1999
Settore MAT/09 - RICERCA OPERATIVA
English
Intervento a convegno
Confessore, G., Dell'Olmo, P., Giordani, S. (1999). A linear time approximation algorithm for a storage allocation problem. In SYSTEMS MODELLING AND OPTIMIZATION (pp.253-260). BOCA RATON : CRC PRESS-TAYLOR & FRANCIS GROUP.
Confessore, G; Dell'Olmo, P; Giordani, S
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/2108/52237
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact