Ślusarek, Maciej NP-completeness of storage allocation. (English) Zbl 0639.68007 Zesz. Nauk. Uniw. Jagielloń. 818, Pr. Inf. 3, 7-18 (1987). 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. Cited in 4 Documents MSC: 68N99 Theory of software 68Q25 Analysis of algorithms and problem complexity Keywords:dynamic storage allocation; strong NP-completeness PDFBibTeX XMLCite \textit{M. Ślusarek}, Zesz. Nauk. Uniw. Jagiell., Pr. Inf. 818(3), 7--18 (1987; Zbl 0639.68007)