首 页机构概况机构设置科研人才队伍合作交流研究生教育博士后图书馆创新文化党群园地院重点实验室彭桓武中心信息公开
  学术活动
  您现在的位置:首页 > 学术活动 > 专题学术报告/Seminar
From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
2012-08-07  【 】【打印】【关闭
Institute of Theoretical Physics
Chinese Academy of Sciences
学术报告
Title
题目
From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
Speaker
报告人
Chi Ho Yeung(杨志豪)博士
Aston University, Birmingham, UK
Date
日期
2012-08-07 PM 16:00 Tuesday
Venue
地点
Conference Hall 322, ITP/理论物理所322报告厅
Abstract
摘要
Optimizing paths on networks is crucial for many applications, from subway traffic to Internet communication. As global path optimization that takes account of all path-choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing sub-optimal solutions. We employ thephysics of interacting polymers and disordered systems to analyzemacroscopic properties of generic path-optimization problems andderive a simple, principled, generic and distributive routing algorithm capable of considering simultaneously all individual path choices. We demonstrate the efficacy of the new 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, which facilitate better understanding of the appropriate operational regimes and their limitations that are difficult to obtain otherwise.
IE6.0浏览器,1024X768分辨率 版权所有 ? 中国科学院理论物理研究所
地址:北京市海淀区中关村东路55号 邮政编码:100190
京ICP备05002865号】 京公网安备1101080094号