ISBN 9783843942027

978-3-8439-4202-7, Reihe Mathematik

Marco Vincenzo Natale
On Packing and Partitioning Problems with Applications to DRAM Allocation

177 Seiten, Dissertation Technische Universität Kaiserslautern (2019), Softcover, A5

Zusammenfassung / Abstract

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.