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