*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Braess's Paradox in Expanders
Abstract:
Expander graphs are known to facilitate effective routing and most real-world networks have expansion properties. At the other extreme, it has been shown that in some special graphs, removing certain edges can lead to more efficient routing. This phenomenon is known as Braess¹s paradox and is usually regarded as a rare event. In contrast to what one might expect, we show that Braess¹s paradox is ubiquitous in expander graphs. Specifically, we prove that Braess¹s paradox occurs in a large class of expander graphs with continuous convex latency functions. Our results extend previous work which held only when the graph was both denser and random and for random linear latency functions. We identify deterministic sufficient conditions for a graph with as few as a linear number of edges, such that Braess¹s Paradox almost always occurs, with respect to a general family of random latency functions. (Joint work with Fan Chung and Wenbo Zhao.)
