@Article{KLRTx87,
author = { R[ichard] M. Karp and F[rank] T. Leighton and R[onald] L. Rivest
and U[mesh] V. Vazirani and V[ijay] V. Vazirani },
title = { Global wire routing in two-dimensional arrays },
journal = { Algorithmica },
publisher = { Springer },
issn = { 0178-4617 },
OPTyear = { 1987 },
date = { 1987 },
volume = { 2 },
number = { 1 },
pages = { 113--129 },
doi = { 10.1007/BF01840353 },
keywords = { Global routing, gate arrays, integer programming, linear
programming, computer-aided design for integrated circuits },
abstract = {
We examine the problem of routing wires of a VLSI chip, where the pins to
be connected are arranged in a regular rectangular array. We obtain tight
bounds for the worst-case ``channel-width'' needed to route an $n \times n$
array, and develop provably good heuristics for the general case. Single-turn
routings are proved to be near-optimal in the worst-case.
\par
A central result of our paper is a ``rounding algorithm'' for obtaining integral
approximations to solutions of linear equations. Given a matrix $\mathbf{A}$ and
a real vector $\mathbf{x}$, then we can find an integral $\mathbf{\hat{x}}$
such that for all $i$, $|\mathbf{\hat{x}_i}-\mathbf{x_i}|<1$ and
$(\mathbf{A\hat{x}})_i-(\mathbf{Ax})_i)<\Delta$. Our error bound $\Delta$
is defined in terms of sign-segregated column sums of $\mathbf{A}$:
\[
\Delta = \max_j \left( \max\left{\sum_{i:a_{ij}>0} a_{ij},\sum_{i:a_{ij}<0} -a_{ij}\right}\right).
\]
},
}