Minimizing channel density by lateral shifting of components

We consider a channel layout model in which we are free to change the spacing, but not the ordering, of the components on the top and bottom of a routing channel. The goal is to minimize channel density. Let N be the total number of terminals on top and bottom components. The main previous approach to this problem used dynamic programming and restricted the potential locations for components and their terminals to grid points along a one-dimensional line, yielding running times polynomial in L, where L is the length of the grid. To use such an algorithm in an environment where high-precision placement is possible, however, one must have a very fine grid, with L growing as Ω(N²) or worse. Consequently, the running time could grow very large as a function of N. We prove a key combinatorial lemma that implies that the run time for a grid-free dynamic programming algorithm can be polynomially bounded. Based on this lemma, a naive O(N⁵) algorithm is derived. We then show how this can be sped up to O(N³) by computing appropriately defined auxiliary functions. For certain instances of the problem in which all components are roughly the same size and have roughly √N terminals, we can further reduce the running time to O(N^2.5).