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 algorithmcolouringsinterval graphsdynamic storage allocation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Inventory, storage, reservoirs (90B05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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