Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

Jens Vygen - Bonn

Faster resource sharing in theory and practice

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

Tobias Müller - Amsterdam

Hamilton cycles in random geometric graphs

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)