On Packing and Partitioning Problems with Applications to DRAM Allocation

In this thesis, we introduce several optimization problems that can be categorized into the classes of packing and partitioning problems. They originate from a real-world application coming from the field of electrical engineering. More precisely, it addresses the issue of the so called memory wall which describes the phenomenon of an increasing gap between the bandwidth requirements of modern Systems-on-a-Chip and the data rate delivered by Dynamic Random Access Memory (DRAM). These problems consist of an input sequence and three numerical parameters. We investigate the complexity and approximability of these DRAM allocation problems with respect to the different parameters and under certain structural restrictions on the input sequence.