Unconstrained Memory Allocation Problem
María Soto, André Rossi, Marc Sevaux, Johann Laurent, Narendra Jussien · 2012
This chapter describes the first version of the memory allocation problem. This version is related to hardware optimization techniques and is focused on the memory architecture design of an embedded system. First, the chapter presents a mathematical formulation for the unconstrained memory allocation problem. Then, the chapter describes that addressing this problem is equivalent to finding the chromatic number of a conflict graph. Next, it presents an example of the unconstrained memory allocation problem. Further, the chapter introduces three new upper bounds on the chromatic number, without making any assumption on the graph structure. The computational complexity of the three-bound computation is assessed. Theoretical and computational comparisons are also made with five well-known bounds from the literature, which demonstrate the superiority of the new upper bounds.