MATHEMATICAL ENGINEERING TECHNICAL REPORTS Multicasting in Linear Deterministic Relay Network by Matrix Completion
Tasuku Soma · 2013
We provide a deterministic polynomial time algorithm for multicasting in a linear deterministic relay network proposed by Avestimehr, Diggavi and Tse (2011). The running time of our algorithm matches the complexity of unicast computations for each sinks, i.e., our algorithm is optimal in this sense. Our approach is based on the polylinking flow model of Goemans, Iwata and Zenklusen (2012), and the mixed matrix completion technique of Harvey, Karger and Murota (2005).