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

dmtcs:2083 - Discrete Mathematics & Theoretical Computer Science, November 24, 2014, Vol. 16 no. 3 - https://doi.org/10.46298/dmtcs.2083
Generalized dynamic storage allocationArticle

Authors: H. A. Kierstead 1; Karin R. Saoub 2

  • 1 School of Mathematical and Statistical Sciences (Arizona, Tempe)
  • 2 Department of Mathematics, Computer Science and Physics (Salem, Virginia, USA)

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.


Volume: Vol. 16 no. 3
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]

Consultation statistics

This page has been seen 348 times.
This article's PDF has been downloaded 402 times.