| Interconnect delay, especially global interconnect delay has become the dominating factor and more difficult to model and optimize in very deep sub-micron design. Many techniques have been employed to reduce interconnect delay: interconnect topology optimization, device sizing, wire sizing, buffer insertion, and simultaneous device and interconnect optimization. In this thesis, we study interconnect topology optimization problem, buffer insertion problem, and minimum classification problem.; The buffer insertion problem is formulated as simultaneously constructing Steiner minimum tree and locating potential buffer insertion positions under the constraint that no edge is longer than a given bound R. We show that steinerized rectilinear Steiner minimum spanning tree may approximate it with performance ratio exact 3. By considering special properties of full Steiner trees, this ratio is improved to 2.; Two major objects of topology optimization problem are: minimization of total interconnect wire length and minimization of path length. In rectilinear metric, minimization of path length problem is actually rectilinear Steiner arborescence (RStA) problem. If x-monotone path restriction is removed, this problem becomes symmetric rectilinear Steiner arborescence (SRStA) problem. PTASs to RStA and SRStA are obtained by transforming optimal solutions to RStA and SRStA into simpler structures without increasing cost a lot and optimal solutions of these special structures can be found by dynamic programming algorithm. Which improves previous approximation algorithms with constant performance ratios.; Minimum linear classification (MLC) problem is considered in this thesis. We prove that MLC problem is NP-complete and present two approximation algorithms with performance ratio O(logn). One algorithm is the direct application of greedy algorithms to set cover problem and the other first finds the minimum number of axis-parallel rectangles containing only white or black points and then employs the same greedy algorithm to the transformed set cover problem. |
