Next: MINIMUM TRAVELING REPAIRMAN
Up: Routing Problems
Previous: SHORTEST WEIGHT-CONSTRAINED PATH
  Index
- INSTANCE:
-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
if
[414].
- Comment:
Approximable within
if
.
In APX if
.
The approximation algorithm will work also for nets with more than three gates,
but the running time is exponential in the number of terminals.
Viggo Kann
2000-03-20