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.
Copyright. All Rights Reserved.