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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
