Large communication networks, such as the Web or the Internet, give rise to a number of challenging algorithmic questions. Our increased dependence on networks means that reliability and availability of the communication infrastructure is becoming more critical than ever. This project will consider some of the algorithmic question raised by such networks. The goal of the project is to develop algorithms with provable performance guarantees.
The project focuses on two closely related issues. Over the last 20 years or so, many powerful techniques have been developed for approximation algorithms. This project focuses on developing new algorithmic techniques, and aims to develop new techniques for approximation algorithms, and obtain large improvements in the achievable solution quality for a number of important problems, where the previous techniques failed.
A second goal of the project is to develop algorithmic techniques for the distributed, and selfish environment of large networks, like the Internet. In such settings the traditional approach of algorithm design is not appropriate: there is no single entity that has the information or the power to run such an algorithm. While centralized algorithms cannot be used directly in such selfish environments, there are very strong ties with certain algorithmic techniques and some of the central questions in algorithmic game theory. This project considers two of these issues, cost-sharing and the price of anarchy. The project will develop new methods for designing cost-sharing algorithms, and understanding what environments lead to low price of anarchy. The cost-sharing problem is closely related to the primal dual method of approximation algorithms. Evaluating the price of anarchy is closely related to approximation algorithms based on local search.
