Using Matroids for Wireless Network Information Flow   . . . Abstract & Biography Michel X. Goemans, MIT     4:15 PM, Stata Center, Room 32-141 LIDS Colloquium -   There will be a short reception at 3:45 p.m. on the 6th floor of the Dreyfoos Tower

Abstract & Biography

Abstract: A natural candidate for modeling wireless networks is the Gaussian channel relay model. The capacity of this model, however, is unknown except for simple networks. For this reason, Avestimehr, Diggavi, and Tse have introduced in 2007 a purely deterministic network model (the ADT model) which incorporates key features of wireless models, broadcasting and superposition. Their model allows to approximate the capacity of Gaussian relay networks.

In this talk, I will present a natural matroid extension of classical network flows (a la Ford and Fulkerson) which includes the ADT model as a special case. This extension uses linking systems (also referred to as bimatroids), a lesser known variant of matroids introduced by Schrijver in his Ph.D. thesis in 1978. A max-flow min-cut theorem for this linking flow model, and efficient algorithms can readily be derived from classical results and algorithms for matroid problems, including matroid intersection and matroid union. If time permits, capacitated extensions and their relation to wireless network models will also be discussed; these involve polylinking systems (or polymatroids).

This is based on joint work with Satoru Iwata (Kyoto) and Rico Zenklusen (Zurich).

Biography: Michel Goemans is the inaugural holder of the Leighton Family chair in Applied Mathematics at MIT. He is an ACM Fellow, a Guggenheim Fellow, and a Sloan Fellow. His research in combinatorial optimization and approximation algorithms has been rewarded with the AMS-MPS Fulkerson Prize, twice the SIAM Optimization prize, and the MPS Tucker prize.