Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, September 27, 2012 |
| Time | 11:00 am |
| Concludes | 12:00 pm |
| Location | Gould-Simpson 906 |
| Speaker | Christian Scheideler |
| Title | Professor |
| Affiliation | University of Paderborn, Germany |
Towards Duality of Multicommodity Multiroute Cuts and Flows: Multi-level Ball-Growing
An elementary h-route flow, for an integer h>1, is a set of h edge-disjoint paths between a source and a sink, each path carrying a unit of flow, and an h-route flow is a non-negative linear combination of elementary h-route flows. An h-route cut is a set of edges whose removal decreases the maximum h-route flow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. In my talk I will present an approximate duality theorem for multicommodity h-route cuts and flows, for h<=3: The size of a minimum h-route cut is at least f/h and at most O(f log^4 k), where f is the size of the maximum h-route flow and k is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum h-route cut problemfor h=3 that has an approximation ratio of O(log^4 k). A key ingredient of this algorithm is a novel rounding technique called multilevel ball-growing that I will discuss in detail in my talk. I will also show how to generalize it so that in certain cases it also applies to any constant h>3.
This is joint work with Petr Kolman that was published at STACS 2011 and SODA 2012.
Biography
Christian Scheideler received his M.S. and Ph.D. degrees in computer science from the University of Paderborn, Germany, in 1993 and 1996. He is currently a Full Professor at the Dept. of Computer Science, University of Paderborn. Before that, he was a postdoc at the Weizmann Institute, Israel, for a year; an Assistant Professor at the Johns Hopkins University, USA, for five years; and an Associate Professor at the Technical University of Munich, Germany,
for three years. He is (co)author of more than 100 publications in refereed conferences and
journals and has served on more than 50 conference committees. His main focus is on
distributed algorithms and data structures, network theory (in particular, peer-to-peer systems,
mobile ad-hoc networks, and sensor networks), and the design of algorithms and architectures
for robust and secure distributed systems.