Generalized Dynamic Storage Allocation
H.A. Kierstead, Karin Rebecca Saoub
Abstract
Dynamic Storage Allocation is a problem concerned with storing items
that each have weight and time restrictions. Approximate algorithms
have been constructed through online coloring of interval graphs. We
present a generalization that uses online coloring of tolerance
graphs. We utilize online-with-representation algorithms on tolerance
graphs, which are online algorithms in which the corresponding
tolerance representation of a vertex is also presented. We find
linear bounds for the online-with-representation chromatic number of
various classes of tolerance graphs and apply these results to a
generalization of Dynamic Storage Allocation, giving us a polynomial
time approximation algorithm with linear performance ratio.
Full Text: PDF PostScript