Approximation Algorithms and Algorithmic Game Theory

在过去的15年中，近似算法领域以惊人的速度发展。除了近似算法与实际应用的明显联系之外，另一个机会是使用该领域开发的方法在其他领域取得概念突破。一个突出的例子是与算法博弈论的相对新领域的自然联系，它试图回答新一代分布式系统（包括互联网、P2P系统、网络和无线系统）提出的问题。最近在网络编码方面令人兴奋的工作也与近似算法建立了紧密的联系。此外，这一领域仍然保持着它的兴奋感——人们仍在获得非常基本的见解，尽管速度比20世纪90年代慢，而且一些基本问题仍未得到解决。PI的研究包括两个方面：研究区域的界面，以及研究近似算法中一些尚未解决的基本问题。

The area of approximation algorithms developed at a spectacular rate over the last fifteen years. Besides the obvious ties of approximation algorithms to real applications, another opportunity is using methodology developed in this area to make conceptual breakthroughs in other areas. A prominent example of this is the natural linkup with the relatively new area of algorithmic game theory, which attempts to answer issues raised by the new generation of distributed systems which include the Internet, P2P systems, the web, and wireless systems.Recent exciting work on network coding also establishes strong links with approximation algorithms. Additionally, this area still retains its excitement - very basic insights are still being obtained, though at a slower rate than in the 1990's, and several fundamental problems still remain unsolved. The PI's research involves both aspects: work on the interface of areas as well as work on some fundamental problems remaining open in approximation algorithms.