Begin: Wed, 16. of Oct 2013 ( 2:00 PM)
Location: Fürstenallee 11, Room F1.110
On October 16, 2013, Prof. Martin Dietzfelbinger will give a talk in the context of the SFB 901 colloquium. Title of the talk: Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids.
Abstract:
We consider Kleinberg's celebrated small world graph model, in which a D-dimensional grid $\{0,\dots,n-1\}^D$ is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined independently at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to $\|u-v\|_2^{-D}$. He showed that this makes it possible to route messages efficiently by the greedy strategy: always move the message over a link that brings it closest to the target w.r.t. the Manhattan distance. The expected length of the path found is O((log n)2).
We prove that for fixed D>=2 greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.e., the probability that node u has a particular long range contact v only depends on $\|{u-v}\|_2$. (Before this was known only for D=1.)
For the proof we define a so-called budget game, in which a token travels over a one-dimensional game board from one end to the other, while the player manages a "probability budget". In each round, the player "bets" part of her remaining probability budget on step sizes. The token makes progress by a step size chosen at random according to the player's bet, and depending on this progress, some of the player's bet is removed from her probability budget. We prove a tight lower bound on the expected number of rounds needed in this game. The lower bound for greedy routing in the D-dimensional grid follows by a reduction.
(joint work with Philipp Woelfel, University of Calgary)
