Dynamic storage allocation with limited compaction - complexity and some practical implications (Q1058288)

In the paper, the problem of dynamic memory allocation with limited compaction of contiguous segments, is considered. The particular question to be solved is to find, given the storage state, a free storage space of a given size by reallocating segments whose total size is minimal. The general case of this problem is proved to be NP-hard. It is, however, possible to give a linear time algorithm for solving a restricted case, involving only a few types of segment sizes. Moreover, for the general case several bounds on the storage size ensuring the possibility of finding in linear time a free space of the desired size by reallocating not more than L memory cells, are presented.