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
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
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)