Abstract

Motivated by the applications in routing in data centers, we study the problem of expressing a doubly stochastic matrix as a linear combination using the smallest number of (sub)permutation matrices. The Birkhoff-von Neumann decomposition theorem proves the existence of such a decomposition, but does not give a representation with the smallest number of permutation matrices. In this talk, I will discuss the tractability of this problem from an exact and an approximate viewpoint. This is joint work with Janardhan Kulkarni and Euiwoong Lee.