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.

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.

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.

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.