### 1 — 14:00 — Depth Optimization in Binary Addition

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. This problem basically reduces to computing And-Or paths, i.e., functions $(t_1 \cap (t_2 \cup (t_3 \cap ... t_m) ...))$ for some Boolean variables $t_i$ . We present an algorithm based on Grinchuk that computes an And-Or path circuit with the smallest known depth, which is a depth of $log_2(m) + log_2(log_2(m))$ for all $m \geq 4$. This approaches the best known asymptotic lower bound of $log_2 (m) + log_2 (log_2 (m)) − 5$ due to Commentz-Walter for the minimum depth of any adder circuit. Our technique is based on recursive splitting of the standard And-Or path circuit into smaller circuits for extended And-Or paths.

### 2 — 14:30 — Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem

Uniform cost-distance Steiner trees minimize the sum of the total length and weighted path lengths

from a dedicated root to the other terminals. They are applied when the tree is intended for signal

transmission, e.g. in chip design or telecommunication networks. They are a special case of general

cost-distance Steiner trees, where different distance functions are used for total length and path

lengths.

We improve the best published approximation factor for the uniform cost-distance Steiner tree

problem from 2.39 [15] to 2.05. If we can approximate the minimum-length Steiner tree problem

arbitrarily well, our algorithm achieves an approximation factor arbitrarily close to 1 + 1/sqrt2 . This

bound is tight in the following sense. We also prove the gap 1 + 1/sqrt2 between optimum solutions and

the lower bound which we and all previous approximation algorithms for this problem use.

Similarly to previous approaches, we start with an approximate minimum-length Steiner tree

and split it into subtrees that are later re-connected. To improve the approximation factor, we

split it into components more carefully, taking the cost structure into account, and we significantly

enhance the analysis.

### 3 — 15:00 — Resource Sharing revisited: Local weak duality and optimal convergence

We revisit the (block-angular) min-max resource sharing problem, which is a well-known generalization of fractional packing and the maximum concurrent flow problem. It consists of finding a resource allocation for every customer, such that the maximum resource usage is minimized. Resource sharing has several applications in VLSI design. Among others, it is used to model the global routing problem.

We improve on the currently fastest known FPTAS in various ways.

A major novelty of our analysis is the concept of local weak duality, which illustrates that the algorithm optimizes (close to) independent parts of the instance separately and that the second-highest entry of the computed solution is approximately minimal.

Further, we provide a lower bound on the number of required oracle calls for a natural class of algorithms. Our FPTAS is optimal within this class; its running time matches the lower bound precisely, and thus improves on the previously best-known running time for the primal as well as the dual problem.

### 4 — 15:30 — Decision-guided SAT for hard routing problems

We present a new SAT based algorithm for packing Steiner trees with additional constraints. Such problems arise

as routing problems in chip design with complex design rules. Our approach uses a modification of the standard

CDCL SAT solving algorithm and incorporates strategies similar to ripup-and-reroute. The resulting algorithm is

significantly faster than ILP routers, produces good routings in practice, and guarantees to find a solution if it exists.