Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Wong, K.Y. Michael; Saad, David; Yeung, Chi Ho
Languages: English
Types: Article
Many important problems in communication networks, transportation networks, and logistics networks are solved by the minimization of cost functions. In general, these can be complex optimization problems involving many variables. However, physicists noted that in a network, a node variable (such as the amount of resources of the nodes) is connected to a set of link variables (such as the flow connecting the node), and similarly each link variable is connected to a number of (usually two) node variables. This enables one to break the problem into local components, often arriving at distributive algorithms to solve the problems. Compared with centralized algorithms, distributed algorithms have the advantages of lower computational complexity, and lower communication overhead. Since they have a faster response to local changes of the environment, they are especially useful for networks with evolving conditions. This review will cover message-passing algorithms in applications such as resource allocation, transportation networks, facility location, traffic routing, and stability of power grids.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] J. R. Banavar, F. Colaiori, A. Flammini, A. Maritan, and A. Rinaldo, Topology of the Fittest Transportation Network, Phys. Rev. Lett. 84, 4745 (2000).
    • [2] A. L. Barabási and R. Albert, Science 286, 509 (1999).
    • [3] A. Bernstein, D, Bienstock, D, Hay, M. Uzunoglu, and G. Zussman, Clumbia University, Electrical Engineering Technical Report #2011- 05-06 (2011).
    • [4] D. Bertsekas, Linear Network Optimization (MIT Press, Cambridge MA, 1991).
    • [5] D. Bertsekas and R. Gallager, Data Networks (Prentice Hall, Englewood Cliffs, NJ, 1992).
    • [6] S. Boettcher and A. G. Percus, Phys. Rev. Lett. 86, 5211 (2001).
    • [7] S. Bohn and M. O. Magnasco, Structure, Scaling, and Phase transition in the Optimal Transport Network, Phys. Rev. Lett. 98, 088702 (2007).
    • [8] S. Bounkong, J. van Mourik, and D. Saad, Phys. Rev. E 74, 057101 (2006).
    • [9] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K. K. Saluja, in Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications, WSNA'02, 2002 (ACM, New York, 2002), pp. 42-48.
    • [10] J. R. L. de Almeida and D. J. Thouless, J. Phys. A: Math. Gen. 11, 983 (1978).
    • [11] R. L. Devaney, An Introduction to Chaotic Dynamical Systems (Redwood City, CA: Addison-Wesley, 1989).
    • [12] E. W. Dijkstra, Numerische Mathematik 1, 269 (1959).
    • [13] P. G. Doyle and J. L. Snell, Random Walks and Electric Networks (Mathematical Association of America, 1984).
    • [14] M. Durand, Structure of Optimal Transport Networks Subject to a Global Constraint, Phys. Rev. Lett. 98, 088701 (2007).
    • [15] B. J. Frey, Graphical Models for Machine Learning and Digital Communication (MIT Press, Cambridge, MA, 1998).
    • [16] E. Harrison, D. Saad, and K. Y. M. Wong, 2nd International Conference on Intelligent Green Building and Smart Grid (IGBSG 2016), Prague, Czech Republic, 27-29 June 2016 (2016).
    • [17] E. Harrison, D. Saad, and K. Y. M. Wong, Int. J. of Smart Grid and Clean Energy, accepted (2016).
    • [18] H. Huang, J. Raymond and K. Y. M. Wong, J. Stat. Phys. 156, 301 (2014).
    • [19] F. P. Kelly, Phil. Trans. R. Soc. Lond. A 337, 343 (1991).
    • [20] S. Kirkpatrick and B. Selman, Science 264, 1297 (1994).
    • [21] F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborová, Phys. Rev. X 2, 021005 (2012).
    • [22] M. Mézard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond (World Scientific, Singapore, 1987).
    • [23] M. Mézard and R. Zecchina, Phys. Rev. E 66, 056126 (2002).
    • [24] A. E. Motter and Y.-C. Lai, Phys. Rev. E 66, 065102 (2002).
    • [25] R. Mulet, A. Pagnani, M. Weigt, and R. Zecchina, Phys. Rev. Lett. 89, 268701 (2002).
    • [26] H. Nishimori, Statistical Physics of Spin Glasses and Information Processing (Oxford University Press, Oxford, 2001).
    • [27] R. T. Rockafellar, Network Flows and Monotropic Optimization (Wiley, 1984).
    • [28] B. Selman, H. Kautz, and B. Cohen, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26 (Providence, RI: American Mathematical Society), 521 (1996).
    • [29] F. Shahrokhi and D. W. Matula, J. of ACM 37, 318 (1990).
    • [30] Z. Shao and H. Zhou, Optimal Transportation Network with Concave Cost Functions: Loop Analysis and Algorithms, Phys. Rev. E 75, 066112 (2007).
    • [31] D. J. Thouless, P. W. Anderson, and R. G. Palmer, Phil. Mag. 35, 593 (1977).
    • [32] K. Y. M. Wong and D. Saad, Phys. Rev. E. 74, 010104(R) (2006).
    • [33] K. Y. M. Wong and D. Saad, Phys. Rev. E 76, 011115 (2007).
    • [34] C. H. Yeung, D. Saad and K. Y. M. Wong, Proc. Natl. Acad. Sci. USA 110, 13717-13722 (2013).
    • [35] C. H. Yeung and K. Y. M. Wong, Phys. Rev. E 80, 021102 (2009).
    • [36] C. H. Yeung and K. Y. M. Wong, Stat. Mech., P03029 (2009).
    • [37] C. H. Yeung and K. Y. M. Wong, Europhys. J. B 74, 227 (2010).
    • [38] C. H. Yeung and K. Y. M. Wong, J. Stat. Mech., P04017 (2010).
    • [39] C. H. Yeung, K. Y. M. Wong, and B. Li, Phys. Rev. E 89, 062805 (2014).
    • [40] J. Zhou and H. Zhou, Phys. Rev. E 79, 020103(R) (2009).
    • [41] Y. Zou and K. Chakrabarty, in Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, INFOCOM 2003, San Francisco, CA (IEEE, Piscataway, NJ, 2003), Vol. 2, pp. 1293-1303.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article