Guillotine Cut in Approximation Algorithms

Ding-zhu Du
University of Minnesota

Guillotine cut as an important technique for designing approximation algorithm was introduced in 1985 for minimum edge-length rectangular partition problem. Later, it becomes an important approach to design polynomial-time approximation schemes for geometric optimization problems. In this talk, we overview this approach and tell you some interesting historical stories and applications in VLSI designs.

Back to Multilevel Optimization in VLSICAD