An Approximation Algorithm for Manhattan Routing

Abstract

Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, we identify a second important measure of difficulty, which we call flux. We show that flux, like density, is a lower bound on channel width. In addition, we present a linear-time algorithm which routes any multipoint net Manhattan routing problem with density d and flux f in a channel of width 2d+O(f). (For 2-point net, the bound is d+O(f).) Thus we show that Manhattan routing is one of the NP-complete problems for which there is a provably good approximation algorithm.