A CELL-BASED HIERARCHICAL PITCHMATCHING COMPACTION USING MINIMAL LP

We describe a new linear programming (LP)-based hierarchical pitchmatc hing method. With a simplified treatment of the intercell constraints, the size of the LP problems is significantly reduced as compared to t he best known results. In particular, the pitchmatching problem is dec omposed into independent subproblems bg exploiting the layout slicing structure. Each subproblem is further ''folded'' to reduce the LP prob lem size, We prove that the new method generates smaller LP problem th an the previously best known approach. Experimental data show that the LP problem size can be 10 times smaller.