NDLI: From the physics of interacting polymers to optimizing routes on the London Underground

Content Provider	PubMed Central
Author	Yeung, Chi Ho Saad, David Wong, K. Y. Michael
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.
Related Links	http://dx.doi.org/10.1073/pnas.1301111110
Ending Page	13722
Page Count	6
Starting Page	13717
File Format	PDF
ISSN	00278424
e-ISSN	10916490
Journal	Proceedings of the National Academy of Sciences of the United States of America
Issue Number	34
Volume Number	110
Language	English
Publisher	National Academy of Sciences
Publisher Date	2013-08-20
Access Restriction	Open
Rights Holder	National Academy of Sciences
Subject Keyword	General Research in Higher Education
Content Type	Text
Resource Type	Article
Subject	Multidisciplinary

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

From the physics of interacting polymers to optimizing routes on the London Underground.

From the Physics of Interacting Polymers to Optimizing Routes on the London Underground

From biosilicification to tailored materials: Optimizing hydrophobic domains and resistance to protonation of polyamines

Effect of station design on death in the London Underground: observational study

On the Relations of the Mortality from Cholera in London to the General Mortality and Temperature

Shedding light on an underground problem

Optimizing the temporal dynamics of light to human perception

Savanna chimpanzees use tools to harvest the underground storage organs of plants

Multiple routes lead to the native state in the energy landscape of the β-trefoil family

From the physics of interacting polymers to optimizing routes on the London Underground

Similar Documents

From the physics of interacting polymers to optimizing routes on the London Underground.

From the Physics of Interacting Polymers to Optimizing Routes on the London Underground

From biosilicification to tailored materials: Optimizing hydrophobic domains and resistance to protonation of polyamines

Effect of station design on death in the London Underground: observational study

On the Relations of the Mortality from Cholera in London to the General Mortality and Temperature

Shedding light on an underground problem

Optimizing the temporal dynamics of light to human perception

Savanna chimpanzees use tools to harvest the underground storage organs of plants

Multiple routes lead to the native state in the energy landscape of the β-trefoil family

From the physics of interacting polymers to optimizing routes on the London Underground