On the Langberg–Médard multiple unicast conjecture

Abstract

A version of the multiple unicast conjecture, proposed by Langberg and Médard (in: Proceedings of 47th annual Allerton, 2009), says that, there exists an undirected fractional multi-commodity flow, or simply, multi-flow, with rate (1,1,…,1) for strongly reachable networks. In this paper, we propose a nonsmooth matrix optimization problem to attack this conjecture: By giving upper and lower bounds on the objective value, we prove that there exists a multi-flow with rate at least (8/9,8/9,…,8/9) for such networks; on the other hand though, we show that the rate of any multi-flow constructed using this framework cannot exceed (1,1,…,1).