MINIMUM RECTILINEAR GLOBAL ROUTING

• INSTANCE: $m\times n$-array of gates, collection C of nets, i.e., 3-sets of gates.

• SOLUTION: Wires following rectilinear paths connecting the gates in each net.

• MEASURE: The largest number of wires in the same channel between two gates in the array.

  
  

• Good News: Admits a $\mbox{\sc PTAS}^\infty$ if $\mbox{\sl opt}\in\omega(\ln(mn))$ [414].

• Comment: Approximable within $1+(e-1)\sqrt{2\ln(mn)/\mbox{\sl opt}}$ if $\mbox{\sl opt}>2\ln(mn)$. In APX if $\mbox{\sl opt}\in\Omega(\ln(mn))$. The approximation algorithm will work also for nets with more than three gates, but the running time is exponential in the number of terminals.