|
CS Home
Dept Info/Contacts
People
Research
Events
Courses
Undergrad Programs:
Computer Science
Informatics
Graduate Program
Prospective Students
Faculty Hiring
Employment
Resources
Help Lab Hours
Student Groups
Support the Department: Weeg Professorship
|
|
Rambling After All These Years
Prof. Yale Patt
Ernest Cockrell, Jr. Centennial Chair in Engineering
University of Texas at Austin
Friday, February 06, 2009
4:00-5:00pm, 140 SH
Abstract
Distributed approximation algorithms tradeoff optimality of the
solution for the amount of resources consumed by the algorithm. This
talk will present recent results on the design and analysis of
efficient distributed approximation algorithms for fundamental network
optimization problems including the minimum spanning tree (MST), the
minimum Steiner tree and related problems, and the shortest paths
problem. I will focus on a simple scheme called the Nearest Neighbor
Tree (NNT) scheme and show how it leads to the first efficient
distributed logarithmic-approximation algorithm for MST in arbitrary
networks. Significantly, our result also shows that there can be an
exponential time gap between exact and approximate distributed MST
computation. Another consequence of our result is that an approximate
MST in unit-disk graphs (which are popular models of wireless
networks) and in random weighted networks (which can model power-law
networks such as the Internet and peer-to-peer networks) can be found
in almost optimal time in a simple and local fashion.
I will then briefly discuss a uniform approach to designing
distributed approximation algorithms using probabilistic tree
embeddings. This approach leads to the first-known time-optimal
distributed logarithmic-approximation algorithms for many problems
including the generalized Steiner forest and shortest paths
problem. It also leads to an improved leader election algorithm in
synchronous networks that is both time optimal and almost message
optimal, thus partially answering an important open problem raised by
David Peleg in 1990.
I will conclude with a discussion on our recent results on designing
energy-efficient distributed algorithms for wireless networks. Our
results initiate a distributed algorithmic theory that uses energy
complexity as a new performance measure to analyze distributed
algorithms.
|
