Approximation Algorithms and Applications in Network Games

点击翻译按钮获取中文摘要

Large communication networks, such as the Web or the Internet, give rise to a number of challenging algorithmic questions. Our increased dependence onnetworks means that reliability and availability of the communicationinfrastructure is becoming more critical than ever. This project will considersome of the algorithmic question raised by such networks. The goal ofthe 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 theprice of anarchy. The project will develop new methods for designingcost-sharing algorithms, and understanding what environments lead tolow 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.