Efficient via shifting algorithms in channel compaction

Considers in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v_c, w_c be the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. The authors define the expected height of columns c in S to be h_c=Av_c+Bw_c +C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let H_S=max_ch_c be the expected height of the critical column(s) of S. H_S is an estimation of the height of S after compaction. The authors show that the problem of shifting vias to minimize H_S can be solved optimally in polynomial time