Linked Decompositions of Networks and Polya Urns with Choice
We propose a novel graph decomposition that enables a scalable form of internet routing with roughly sqrt(n) memory and logarithmic delay. Subnetworks are required to be small and with small diameter, no three of them to overlap, but any two of them to do so. Our main result is that several popular models of “internet-like graphs”, most importantly the preferential attachment one proposed by Barabasi et al. in 1999, have such decompositions almost surely; experiments show that so does the real internet. Part of our analysis involves a variant of the Polya urn model in which we have a choice between two or more urns; in contrast to the traditional Polya urn model, this twist results in very balanced loads. (Joint work with Henry Lin, Christos Amanatidis, Martha Sideri, and Dick Karp.)
Speaker Details
Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before Berkeley he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written four textbooks and many articles on algorithms, complexity, and their applications to optimization, databases, AI, economics, and the Internet. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich), the University of Macedonia (Thessaloniki) and the University of Athens. He is a member of the American Academy of Arts and Sciences and of the National Academy of Engineering, and a fellow of the ACM. His novel “Turing (a novel about computation),” was published by MIT Press in 2003.
- Date:
- Speakers:
- Christos Papadimitriou
- Affiliation:
- University of California, Berkeley
-
-
Jeff Running
-
