Approximation Algorithms and Algorithmic Game Theory

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

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.