An Optimization Approach to the Langberg-Medard Multiple Unicast Conjecture

Abstract

The Langberg-Medard multiple unicast conjecture claims that for any strongly reachable k-pair network, there exists a multi-flow with rate (1, 1, ..., 1). In this talk, we will examine an optimization problem that is closely related to this conjecture. We will construct a sequence of asymptotically optimal solutions to the aforementioned optimization problem, based on which, we propose a perturbation framework, which not only promises a better solution for any k but also solves the optimization problem for the cases k = 3, 4, ..., 10, accordingly yielding multi-flows with the largest rate to date.