Kierstead, H. A. and Saoub, Karin R. - Generalized dynamic storage allocation

dmtcs:2083 - Discrete Mathematics & Theoretical Computer Science, November 24, 2014, Vol. 16 no. 3 (in progress)
Generalized dynamic storage allocation

Authors: Kierstead, H. A. and Saoub, Karin R.

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.


Source : oai:HAL:hal-01188897v1
Volume: Vol. 16 no. 3 (in progress)
Section: Graph Theory
Published on: November 24, 2014
Submitted on: February 25, 2014
Keywords: online coloring,dynamic storage allocation,tolerance graphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 22 times.
This article's PDF has been downloaded 91 times.