A polynomial time approximation algorithm for dynamic storage allocation (Q1176726)

The NP-complete problem Dynamic Storage Allocation may be phrased in terms of `weighted' colourings of weighted interval graphs. It is shown how an on-line algorithm for colouring interval graphs (which is a modification of an algorithm of Kierstead and Trotter) may be used to construct a polynomial time approximation algorithm for the Dynamic Storage Allocation problem. The performance ratio is at most 6; the best previously known performance ratio for such an algorithm had been 80.