Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


From Wireless Information Flows to Matroids

In this talk, I will give a brief introduction to matroids and highlight one concrete and arguably surprising application to wireless information flows.

Matroids are a rich combinatorial structure which, in short, can be described as characterizing problems that can be solved through a simple greedy algorithm. At first sight, this viewpoint on matroids can easily be deceiving, giving the impression that matroids may only capture very simple problems. However, the rich combinatorial structure of matroids, and various results from algorithmic matroid theory, can be exploited to tackle highly non-trivial combinatorial problems in a unifying framework.

We exemplify this by considering a deterministic model for wireless information flows introduced by Avestimehr, Diggavi, and Tse (the ADT model), and present a strong connection of this model to matroids. Once this connection is established, we can cast results from algorithmic matroid theory to the ADT model. In particular, we thus obtain a fast procedure to determine an optimal coding strategy, a natural max-flow min-cut theorem, and the possibility to optimize over interesting extensions of the ADT model.

Based on joint work with Michel Goemans and Satoru Iwata.

Type of Seminar:
Control Seminar Series
Prof. Rico Zenklusen
ETH Zurich - Institut for Operations Research
Nov 29, 2017   17:15 h

Contact Person:

No downloadable files available.
Biographical Sketch:
Rico Zenklusen is an Assistant Professor in the Mathematics Department at ETH Zurich, heading the Combinatorial Optimization Group. Prior to joining ETH Zurich, Rico was on the faculty of the Johns Hopkins University, in the Department of Applied Mathematics and Statistics. Before that, he worked several years as a postdoc at MIT, and also shortly at EPFL. Rico holds a PhD from ETH Zurich and a master's degree from EPFL. His main research interests lie broadly in Combinatorial Optimization and its applications, with a focus on techniques related to polyhedra, (poly-)matroids, and submodular functions.