Approximation Algorithms and Applications in Network Games

大型通信网络，如Web或Internet，产生了许多具有挑战性的算法问题。我们对网络的日益依赖意味着通信基础设施的可靠性和可用性变得比以往任何时候都更加重要。该项目将解决此类网络提出的一些算法问题。该项目的目标是开发具有可证明性能保证的算法。在过去的20年左右，许多强大的技术已经开发的近似算法。该项目的重点是开发新的算法技术，旨在开发新的近似算法技术，并在一些重要问题的可实现的解决方案质量方面取得很大的改进，其中以前的技术失败了。该项目的第二个目标是开发分布式算法技术，以及大型网络的自私环境，如互联网。在这种情况下，传统的算法设计方法是不合适的：没有一个实体拥有运行这种算法的信息或权力。虽然集中式算法不能直接用于这种自私的环境中，但它与某些算法技术和算法博弈论中的一些核心问题有着非常紧密的联系。这个项目考虑了其中的两个问题，成本分摊和无政府状态的代价。该项目将开发设计成本分摊算法的新方法，并了解什么环境导致低成本的无政府状态。费用分摊问题与近似算法的原始对偶方法密切相关。评估无政府状态的代价与基于局部搜索的近似算法密切相关。

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.