New approximation techniques for some ordering problems
Satish S. Rao, Andréa W. Richa · 1998
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 \\Omega\\Gamma/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...