A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation

摘要

We have presented a polynomial-time algorithm based on Dynamic Programming for the Slice- able rectilinear partitioning problem. The above al- gorithm, though polynomial time, might still be re- garded as having a high complexity for practical appli- cations. Various approaches, such as greedy methods, neural networks, and genetic algorithms can be used to improve the complexity at the expense of optimality. A greedy variation with simulated annealing of the Above algorithm has been implemented for isolating Defect areas in the mask in IBM Microelectronics Di- Vision.