Yeung, Chi H., Saad, David and Wong, K.Y. Michael (2013). From the physics of interacting polymers to optimizing routes on the London Underground. Proceedings of the National Academy of Sciences, 110 (34), pp. 13717-13722.
Abstract
Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use the physics of interacting polymers and disordered systems to analyze macroscopic properties of generic path optimization problems and derive a simple, principled, generic, and distributed routing algorithm capable of considering all individual path choices simultaneously. We demonstrate the efficacy of the algorithm by applying it to: (i) random graphs resembling Internet overlay networks, (ii) travel on the London Underground network based on Oyster card data, and (iii ) the global airport network. Analytically derived macroscopic properties give rise to insightful new routing phenomena, including phase transitions and scaling laws, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.
Publication DOI: | https://doi.org/10.1073/pnas.1301111110 |
---|---|
Divisions: | College of Engineering & Physical Sciences > Systems analytics research institute (SARI) |
Uncontrolled Keywords: | General |
Publication ISSN: | 1091-6490 |
Last Modified: | 12 Aug 2024 07:01 |
Date Deposited: | 03 Sep 2013 13:21 |
Full Text Link: |
http://www.pnas ... nt/110/34/13717 |
Related URLs: |
http://www.scop ... tnerID=8YFLogxK
(Scopus URL) |
PURE Output Type: | Article |
Published Date: | 2013-08-20 |
Published Online Date: | 2013-07-29 |
Authors: |
Yeung, Chi H.
Saad, David ( ![]() Wong, K.Y. Michael |