The Gaussian relay network is a natural candidate to model wireless networks. Unfortunately, it is not known how to determine the capacity of this model, except for very simple network topologies. For this reason, in 2007, Avestimehr, Diggavi, and Tse introduced a purely deterministic network model (the ADT model), which approximates the Gaussian relay network by capturing two key properties of wireless channels, namely broadcast and superposition. The ADT model attracted considerable attention because its capacity can be determined efficiently. Furthermore, as shown in 2009 by Amaudruz and Fragouli, also an optimal coding strategy for the ADT network can be found in polynomial time.
In this talk, I will show a strong connection between the ADT model and matroid optimization, which is a well-established field in combinatorial optimization. This connection allows us to exploit strong algorithmic and structural results from matroid optimization to optimize and analyze ADT networks. In particular, standard matroid optimization algorithms can be used to find an optimal coding strategy very efficiently, and structural results on matroids translate into interesting properties of the ADT model, like a max-flow min-cut theorem. The additional abstraction obtained by rephrasing the ADT model in the context of matroids furthermore allows us to tackle a variety of generalizations of the ADT model.
The goal of this talk is twofold. Apart from showing how to find optimal coding strategies for the ADT model, I want to give a quick introduction to the field of matroid optimization, which is an interesting algorithmic toolbox with numerous applications beyond network coding.
Based on joint work with Michel Goemans and Satoru Iwata.
Speaker Biography
Rico Zenklusen is an assistant professor in the Department of Applied Mathematics and Statistics at Johns Hopkins University. He received his PhD from ETH Zurich in 2008 and was a postdoc at EPFL and MIT before joining Johns Hopkins. His main research interests are in Combinatorial Optimization and its interfaces with Operations Research and Computer Science.