Optimization via communication networks

It has been known since the early 1990s that backpressure-type algorithms for communication networks (such as the Max-Weight algorithm) can be used to approximately solve static optimization problems such as Maximum Concurrent Flow problems. However, the running time of this approach is not fully understood. In this survey paper we shall describe the best currently known bounds and also compare the running time of the Max-Weight algorithm (which uses additive weights) with that of multiplicative weight schemes such as the Garg-Konemann algorithm [7].