This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Dell'Olmo P., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 448  (Previous ) 


Confessore G., Dell'Olmo P., Giordani S.

An approximation algorithm for proper dynamic storage allocation

ABSTRACT

A general instance of the Dynamic Storage Allocation (DSA) problem can be represented by an interval graph, where vertices correspond to items and there is an edge between two vertices whenever the corresponding items have to be allocated during overlapping time intervals. When the intervals are inclusion-free, the instance induces a proper interval graph and we call the problem Proper Dynamic Storage Allocation (PDSA). We prove that the PDSA problem is NP-hard and propose a polynomial time approximation algorithm, whose performance ratio is bounded by 2. The bound is shown to be tight.