An Oxford-Warwick Joint Seminar Afternoon will be held in the Mathematical Institute, University of Oxford on Tuesday 10 November 2009. The schedule is as follows:
2.00 pm Harald Raecke (Warwick)
Oblivious Routing in the L_p norm
2.50 pm Colin
McDiarmid (Oxford)
Random
graphs with few disjoint cycles
3.40 pm Tea
4.30 pm Gregory Sorkin (IBM Research, NY)
The Power of Choice in a Generalized Polya Urn Model
The first two talks will be in L3 and the third in SR2. Abstracts can be found below. Further details can be obtained from Alex Scott (contact form).
Harald Raecke (Warwick), Oblivious Routing in the L_p norm
Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph G=(V,E) is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.
We show the existence of an oblivious routing scheme with competitive ratio O(log n) and a lower bound of Omega(log n/loglog n) for this model when the aggregation function agg is an L_p-norm.
Our results can also be viewed as a generalization of the
work on approximating metrics by a distribution over dominating tree metrics and
the work on minimum congestion oblivious. We provide a convex combination of
trees such that routing according to the tree distribution approximately
minimizes the L_p-norm of the link loads. The embedding techniques of Bartal and
Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the
L_1-norm while the result on congestion minmizing oblivious routing solves it
for L_\infty. We give a single proof that shows the existence of a good
tree-based oblivious routing for any L_p-norm.
Colin McDiarmid (Oxford), Random graphs with few disjoint cycles
Fix a positive integer $k$, and consider the class of all
graphs which do not have $k+1$ vertex-disjoint cycles. A classical result of
Erd\H{o}s and P\'{o}sa says that each such graph $G$ contains a blocker of size
at most $f(k)$. Here a {\em blocker} is a set $B$ of vertices such that $G-B$
has no cycles.
We give a minor extension of this result, and deduce that
almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of
size $k$. This yields an asymptotic counting formula for such graphs; and
allows us to deduce further properties of a graph $R_n$ taken uniformly at
random from the class: we see for example that the probability that $R_n$ is
connected tends to a specified limit as $n \to \infty$.
There are corresponding results when we consider unlabelled graphs with few
disjoint cycles. We consider also variants of the problem involving for example
disjoint long cycles.
This is joint work with Valentas Kurauskas and Mihyun Kang.
Gregory Sorkin (IBM Research, NY), The Power of Choice in a Generalized Polya Urn Model
We introduce a "Polya choice" urn model combining elements
of the well known "power of two choices" model and the "rich get richer" model.
From a set of $k$ urns, randomly choose $c$ distinct urns with probability
proportional to the product of a power $\gamma>0$ of their occupancies, and
increment one with the smallest occupancy. The model has an interesting phase
transition. If $\gamma \leq 1$, the urn occupancies are asymptotically equal
with probability 1. For $\gamma>1$, this still occurs with positive probability,
but there is also positive probability that some urns get only finitely many
balls while others get infinitely many.