Algorithms for Interval Coloring, Geometric Packing and Memory Optimization

The dissertation is concerned with design and analysis
of algorithms for a number of computational problems
that can be formulated as interval coloring of
geometric intersection graphs.
We propose a novel approach to these computational problems
that is based on both geometric packing
and classic coloring of geometric intersection graphs.
One of the main problems we are interested in
is Dynamic Storage Allocation.
All previous algorithms for this computational problem
are based on online graph coloring, and
the best possible approximation ratio
for algorithms based on online coloring is 6.
We propose a new O(n log n)-time
3-approximation for Dynamic Storage Allocation.
For the problem of Compile-Time Memory Allocation,
we propose the first efficient algorithm
with an explicit performance guarantee.
This algorithm is based on a more precise model
of the underlying computational problem than
the previous algorithms for Compile-Time Memory Allocation.
Another result of this dissertation is an algorithm
for interval coloring of general graphs
based on the concept of local fragmentation.
In contrast to the known interval coloring algorithms,
our algorithm is not a generalization of algorithms
for classic graph coloring.
Extensive experimental results
(using approximately 50000 weighted graphs)
indicate that our algorithm is superior to previous algorithms.