NP-completeness of storage allocation. (English) Zbl 0639.68007

The off-line version of the dynamic storage allocation problem (DSA) is investigated. A proof of its strong NP-completeness is given using a pseudopolynomial transformation from the 3-partition problem. In case of uniform block sizes a polynomial time algorithm solving DSA is presented. The problem remains NP-complete when various restrictions on block lengths (residence times) are introduced, except for instances containing only blocks of lengths 1 and 2. In the last case DSA is polynomial.


68N99 Theory of software
68Q25 Analysis of algorithms and problem complexity