CMU-CS-97-177Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-97-177
Satish Rao*, Andrea W. Richa September 1997
To appear in the
Keywords: Approximation algorithms, networks, graphs, ordering
problems, linear arrangement
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
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 13 pages
*NEC Research Institute, 4 Independence Way, Princeton, NJ 08540, | |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |