New approximation techniques for some ordering problems

We describe logarithmic times optimal approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage--time product. This improves on the best previous approximation bounds of Even, Naor, Rao, and Schieber for these problems by an \\/15 log n) factor. Even, Naor, Rao, and Schieber defined spreading metrics for each of the ordering problems above (and to other problems) ; for each of these problems, they provided a spreading metric of volume W, such that W is a lower bound on the cost of a solution to the problem. They used this spreading metric to find a solution of cost O (W log n log log n) (for simplicity, assume that all tasks have unit processing time in the minimum storage--time product problem). In this paper, we show how to find a solution within a logarithmic factor times W for these problems. We develop a recursion where at each level we identify cost which, if incurred, yi. . .