Second-Order Methods for Distributed Approximate Single-And Multicommodity Flow
The authors study local-control algorithms for maximum flow and multicommodity flow problems in distributed networks. The authors propose a second-order method for accelerating the convergence of the "First-order" distributed algorithms recently proposed by Awerbuch and Leighton. The authors' experimental study shows that second-order methods are significantly faster than the first-order methods for approximate single- and multicommodity flow problems. Furthermore, their experimental study gives valuable insights into the diffusive processes that underly these local-control algorithms; this leads people to identify many open technical problems for theoretical study.