A polynomial time approximation algorithm for dynamic storage allocation

DOI10.1016/0012-365X(91)90011-PzbMath0761.05087MaRDI QIDQ1176726

Henry A. Kierstead

Publication date: 25 June 1992

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithm; colourings; interval graphs; dynamic storage allocation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B05: Inventory, storage, reservoirs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Optimal on-line coloring of circular arc graphs, Dynamic storage allocation with known durations, An approximation result for a periodic allocation problem, First-fit coloring of bounded tolerance graphs, Single and multiple device DSA problems, complexities and online algorithms, An improved algorithm for online coloring of intervals with bandwidth, On spectrum assignment in elastic optical tree-networks, An easy subexponential bound for online chain partitioning, Coloring interval graphs with First-Fit, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, On the interval chromatic number of proper interval graphs, Optimizing bandwidth allocation in elastic optical networks with application to scheduling, A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem

Cites Work

• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation
• The Bay Restaurant--A Linear Storage Problem
• An Estimate of the Store Size Necessary for Dynamic Storage Allocation
• On Woodall's interval problem
• Unnamed Item
• Unnamed Item
• Unnamed Item