# Achievements of Research Area K

## Efficient Algorithms for Combinatorial Optimisation in Networks.

The most basic optimisation problem in networks asks for a shortest path in an undirected graph with nonnegative weights. In chip routing, for example, we need to find approximately 108 such paths in graphs with often more than 1011 vertices. Our new generalised version of Dijkstra’s algorithm [K:PRV09] exploits the graph structure to solve this fundamental problem much faster than any previous algorithm.

If we want to connect more than two terminals, we have the Steiner tree problem in weighted graphs. Vygen found an exact algorithm that is faster than all previous ones in most cases. Karpinski and co-authors improved the best known approximation factor for the Steiner tree problem and the generalised Steiner tree problem [K:BKZ10] with distances 1 and 2. These results advance the state of the art of this classical NP-hard problem significantly.

Often, paths or Steiner trees must be packed subject to various constraints. Many such problems can be formulated as instances of the (block-angular) min-max resource sharing problem. Vygen and co-authors proposed an algorithm [K:MRV11] for this general nonlinear problem that works even with weak block solvers as oracles and is at the same time faster and more general than any previous algorithm, even for the linear special case (which includes the well-known multi-commodity flow problem).

The algorithm is also very efficient in practice. We are now able to solve problems with millions of resources and customers in a few minutes almost optimally [K:MRV11]. In the special case of multi-commodity flows this corresponds to linear programs with approximately 1013 variables and 1013 constraints. Our new algorithm will have many applications in different areas, which we are currently exploring.

We also improved the best known approximation ratio for various other classical problems, including universal facility location [K:Vyg07], sink clustering [K:MV08], the betweenness problem in tournaments [L:KS10], transitive reductions in directed networks, and several optimisation problems in wireless networks. Moreover, Hougardy devised (almost) linear-time approximation algorithms for degree-constrained subgraph problems, including weighted matching, and a linear-time 1.4-approximation algorithm for square packing [K:Hou11].

Another interesting research area is solving very hard problems optimally. Among the hardest fundamental combinatorial problems (both from a theoretical and practical standpoint) are graph coloring [K:HCS11], rectangle packing, and placement. In each of these cases, Held and Hougardy (with co-authors) were able to solve much larger instances than was possible before. Our new techniques include combinations of branch-and-bound with constraint programming or with numerically safe linear programming [K:HCS11].

## Chip Design.

We continued our successful work on chip design, one of the most fruitful and important application areas of mathematics. By advancing the mathematical foundations, developing novel algorithms based on this theory, and implementing these algorithms in efficient software, we have established a direct link between theory and practice. Mathematics helps design better chips, and practical challenges motivate interesting fundamental research questions.

Our most important recent results are substantially improved algorithms for placement, routing, and timing optimisation. Some of these are the first algorithms that guarantee near-optimality. BonnPlace [K:BSV08] is based on analytical placement and our new algorithm for the Hitchcock transportation problem [K:Bre08], recently combined with a novel flow-based partitioning approach. BonnRoute contains an extremely fast global router based on our new resource sharing algorithm [K:MRV11] and a detailed router combining algorithms for on-track (longdistance) connections [K:PRV09] and off-grid pin access. In BonnOpt, our timing optimisation toolkit, our new algorithms for repeater tree topologies [K:BHM+10], buffering, gate sizing, and logic restructuring [K:WRS07] are most notable.

These BonnTools [K:KRV07] are widely used in industry for the design of most complex chips. For example, IBM relies on them for all their advanced chips. They are continuously enhanced to meet new technological challenges and incorporate better and faster algorithms.

We recently widened our application area to microprocessor design, which is traditionally done hierarchically and with a huge amount of manual effort. Besides adapting our existing Bonn-Tools, we developed completely new algorithms for hierarchical problems such as macro placement. With these one can place many instances optimally for the first time.

Currently, we are developing and implementing the first algorithms for routing in technologies with double patterning lithography, which will be predominant at the 14nm technology node, and for fully automated transistor-level layout.

## Activities.

The most notable event of Research Area K was the Bonn Workshop on Combinatorial Optimisation in November 2008, organised by Cook, Korte, Lovász, and Vygen. Most of the top researchers in the field came from all over the world; see www.or.uni-bonn.de/workshop. The proceedings [K:CLV09] contain many surveys by prominent researchers and are a valuable foundation for current and future research. We also organised an innovative spring school on mathematics of chip design in Hangzhou (March/April 2009), sponsored by the DFG and the National Natural Science Foundation of China (NSFC); see www.cs.zju.edu.cn/people/yedeshi/chipdesign09.

The 5th edition of our combinatorial optimisation book [K:KV08] will appear in 2012. This book has been translated into six languages. In our new master’s program we established a regular lecture course on the mathematics of chip design, probably the first such course worldwide. We are currently writing the first mathematical textbook in this area.

We also set up a grant program for outstanding students in Discrete Mathematics. The selected students mentor younger students and conduct many extracurricular activities.