# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, November 8, 2010

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
10623 Berlin

Lecture - 14:15

### Faster resource sharing in theory and practice

Abstract:
We consider the (block-angular) min-max resource sharing problem, which generalizes problems such as multicommodity flows and fractional packing. It is defined as follows. Given finite sets $R$ of resources and $C$ of customers, a convex set $B_c$ (called block), and a convex function $g_c: B_c \to \mathbb{R}^R_{\ge 0}$ for each $c\in C$, the task is to find $b_c\in B_c$ ($c \in C$) approximately attaining $\lambda^* := \inf\{\max_{r\in R}\sum_{c\in C} (g_c(b_c))_r : b_c\in B_c \, (c\in C)\}$. The blocks $B_c$ are given implicitly by oracle functions $f_c : \mathbb{R}^R_{\ge 0} \to B_c$, which for $c \in C$ and $y\in\mathbb{R}^R_{\ge 0}$ return an element $b_c\in B_c$ with $y^{\scriptscriptstyle\top} g_c(b_c) \leq \sigma \inf_{b \in B_c} y^{\scriptscriptstyle\top} g_c(b)$. Here $\sigma\ge 1$ is a given constant. We present a simple combinatorial algorithm that solves this problem with an approximation guarantee $\sigma(1+\omega)$ in $O(\theta (|C|+|R|) \log|R| (\log\log|R|+\omega^{-2}))$ time for any $\omega>0$, where $\theta$ is the time for an oracle call. This generalizes and improves various previous results.
Our work was motivated mainly by global routing in chip design. Here the blocks are mixed-integer sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. We implemented the algorithm and present experimental results on instances resulting from recent industrial chips, with millions of customers and resources. We solve them nearly optimally in less than two hours.
This is joint work with Dirk M\"uller and Klaus Radke.

Colloquium - 16:00

### Hamilton cycles in random geometric graphs

Abstract:
Let X_1,..., X_n be random points from the unit square [0,1]^2 (picked independently, uniformly at random). I will sketch a proof of the fact that if we add edges between these points one by one by order of increasing edge length then, with probability tending to 1 as the number of points n tends to infinity, the first Hamilton cycle (that is, a cycle that visits every point exactly once) appears at precisely the same time the last vertex of degree less than two disappears. This answers a long standing open question of Penrose. Time permitting, I will speak about a number of additional results on Hamilton cycles in random geometric graphs. (joint work with J. Balogh, B. Bollobas, M. Krivelevich and M. Walters)