HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Generalized dynamic storage allocation

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01188897
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 31, 2015 - 5:02:56 PM
Last modification on : Thursday, September 7, 2017 - 1:03:42 AM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:40:58 AM

File

dmtcs-16-3-14.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

H. A. Kierstead, Karin R. Saoub. Generalized dynamic storage allocation. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (3), pp.253--262. ⟨10.46298/dmtcs.2083⟩. ⟨hal-01188897⟩

Share

Metrics

Record views

42

Files downloads

644