language: en

New Approximation Techniques for Some Ordering Problems

Satish Rao Andrea W. Richa

Abstract 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 (log 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, yields subproblems with reduced spreading metric volume. Specifically, we present a divide-and-conquer strategy where the cost of a solution to a problem at a recursive level is C plus the cost of a solution to the subproblems at this level, and where the spreading metric volume on the subproblems is less than the original volume by (C= log n). This ensures that the resulting solution has cost O(log n) times the original spreading metric volume. We note that this is an existentially tight bound on the relationship between the spreading metric volume W and the true optimal values for these problems. For planar graphs, we combine a structural theorem of Klein, Plotkin, and Rao with our new recursion technique to show that the spreading metric cost volumes are within an O(log log n) factor of the cost of an optimal solution for the minimum linear arrangement, and the minimum containing interval graph problems.

[To appear in Proceedings of Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 1998.]

[Research supported by NEC Research Institute, 4 Independence Way, Princeton, NJ 08540; satish@research.nj.nec.com. Research supported in part by NSF NYI Award No. CCR-9457766, ARPA Contract F33615-93-1-1330, NEC Research Institute, and DIMACS. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, aricha@cs.cmu.edu.]

1 Introduction.