Computer Science Department
School of Computer Science, Carnegie Mellon University
New Approximation Techniques for Some Ordering Problems
Satish Rao*, Andrea W. Richa
To appear in the Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1998.
Our techniques are based on using spreading metrics (as in Even, Naor, Rao, and Scheiber) to define a cost estimate for a problem. In this paper, we develop a recursion where at each level we identify cost which, if incurred, yields a reduction in the spreading metric cost estimates for the resulting subproblems. Specifically, we give a strategy where the cost of solving a problem at a recursive level is C plus the cost of solving the subproblems, and where the spreading metric cost estimate on the subproblem(s) is reduced by at least Omega(C/log n). This ensures that the resulting solution has cost at most O(log n) times the original spreading metric cost estimate.
We note that this is an existentially tight bound on the relationship between the spreading metric cost estimates 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 and standard divide-and-conquer techniques to show that the spreading metric cost estimates are within an O(log log n) factor of the cost of the optimal solution for the minimum linear arrangement and the minimum containing interval graph problems.
*NEC Research Institute, 4 Independence Way, Princeton, NJ 08540,