@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).$ }, }