Today, we worked through homeworks.

1.  NP-hard approximation

1.1  Global wiring problem

There is some array of locations. The goal is to connect some pairs of locations in the array. The goal is to minimize the number of wires crossing a boundary between adjacent locations.

Constraints:

• at most one bend.

The problem is NP hard.

The problem can be rewritten as an integer programming problem.

1.2  integer programming formulation

For each pair, N_i , of locations, introduce 2 variables, x_i0,x_i1 .

Let:

• T_b0 = {i|N_i passes through b if x_i0 = 1}
• T_b1 = {i|N_i passes through b if x_i1 = 1}

The integer programming problem is then:

minimize w where

• x_i0,x_i1 Î {0,1}"N_i
• x_i0+x_i1 = 1
• å_{i Î Tb0}x_i0+å_{i Î Tb1}x_i1 £ w

1.3  linear program relaxation

Replace the first constraint with 0 £ x_i0,x_i1 £ 1 to turn the problem into a linear programming problem. The linear programming solution must have W_LP £ W_IP , giving a lower bound on the integer programming solution.