NS Seminar: Paper Presentation

Date and Location

Oct 10, 2016 - 2:00pm to 3:00pm
Network Science Lab, Bldg 434, Room 122


Alex Jones, CS Trainee


Markov Approximation for Combinatorial Network Optimization

Mingua Chen, Soung Chang Liew, Ziyu Shao, and Caihong Kai

Many important network design problems are fundamentally combinatorial optimization problems. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log–sum–exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time-reversible Markov chains. Selected Markov chains among this class yield distributed algorithms that solve the log–sum–exp approximated combinatorial network optimization problem. By examining three applications, we illustrate that the Markov approximation technique not only provides fresh perspectives to existing distributed solutions, but also provides clues leading to the construction of new distributed algorithms in various domains with provable performance. We believe the Markov approximation techniques will find applications in many other network optimization problems.