Theory Seminar: Stephen Young, University of Louisville, Kentucky

Event Details
  • Date/Time:
    • Monday October 8, 2012
      1:05 pm
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

ndongi@cc.gatech.edu

Summaries

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

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.)

 

Additional Information

In Campus Calendar
No
Groups

School of Computer Science, ARC

Invited Audience
No audiences were selected.
Categories
No categories were selected.
Keywords
No keywords were submitted.
Status
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Sep 25, 2012 - 5:25am
  • Last Updated: Oct 7, 2016 - 10:00pm