Markov Approximation for Combinatorial Network Optimization

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

118 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number6532343
Pages (from-to)6301-6327
Journal / PublicationIEEE Transactions on Information Theory
Volume59
Issue number10
Online published14 Jun 2013
Publication statusPublished - Oct 2013
Externally publishedYes

Abstract

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. © 1963-2012 IEEE.

Research Area(s)

  • Combinatorial optimization, distributed algorithms, Markov approximation, time-reversible Markov chains, wireless networks

Citation Format(s)

Markov Approximation for Combinatorial Network Optimization. / Chen, Minghua; Liew, Soung Chang; Shao, Ziyu et al.

In: IEEE Transactions on Information Theory, Vol. 59, No. 10, 6532343, 10.2013, p. 6301-6327.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review