Premium
Braess's Paradox in large random graphs
Author(s) -
Valiant Gregory,
Roughgarden Tim
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20325
Subject(s) - counterintuitive , latency (audio) , computer science , random graph , set (abstract data type) , routing (electronic design automation) , constant (computer programming) , mathematics , mathematical optimization , mathematical economics , theoretical computer science , computer network , graph , physics , telecommunications , quantum mechanics , programming language
Braess's Paradox is the counterintuitive fact that removing edges from a network with “selfish routing” can decrease the latency incurred by traffic in an equilibrium flow. We prove that Braess's Paradox is likely to occur in a natural random network model: with high probability, there is a traffic rate and a set of edges whose removal improves the latency of traffic in an equilibrium flow by a constant factor. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010