欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
科学研究
RESEARCH
Network characterizations for excluding Braess's paradox
时间  Datetime
2020-11-29 14:30 — 15:30
地点  Venue
教室(901)
报告人  Speaker
Xujin Chen (陈旭瑾)
单位  Affiliation
中国科学院
邀请人  Host
吴耀琨
备注  remarks
zoom ID: 99329966093 pw: 107583
报告摘要  Abstract

Braess's paradox exposes a counterintuitive phenomenon that when travelers selfishly choose their routes in a network, removing links can improve overall network performance. Under the model of nonatomic routing, we characterize the topologies of k-commodity undirected and directed networks in which Braess's paradox never occurs. Our results generalize Milchtaich's series-parallel characterization for the single-commodity undirected case, and answer Roughgarden’s open question on characterizing vulnerable graphs. (Joint work with Zhuo Diao and Xiaodong Hu)