Guillotine Cut in Approximation Algorithms

 

Abstract

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 first overview this approach and some of its interesting historical stories, and then discuss its applications in VLSI designs.

Bio of the Speaker

Ding-Zhu Du is an IPA working in NSF as a Program Director for Theory of Computing. He started this job on September 3, 2002. His home institution is University of Minnesota where he is a professor in Department of Computer Science and Engineering. His current research interests include design and analysis of approximation algorithms for combinatorial optimization problems with various applications in computer networking, telecommunication, VLSI designs, etc, especially in wireless networking and mobile computing.  Dr. Du received his Ph.D. from University California at Santa Barbara under supervision of Professor Ronald V. Book in 1985 and his M.S. from Chinese Academy of Sciences in 1982. Before settled in Minnesota, He worked in Mathematical Sciences Research Institute at Berkeley for one year, in Department of Mathematics, MIT for one year, and in Department of Computer Science, Princeton University for one and a half year. Currently, he has published about 140 journal papers and several books. He is the editor-in-chief for Journal of Combinatorial Optimization and also in editorial board for several other journals. There are 21 Ph.D.s graduated under his supervision.

BACK