Approximation Algorithms and Algorithmic Game Theory

近似算法和算法博弈论

• 批准号: 0515186
• 负责人: Vijay Vazirani
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2007-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515186&HistoricalAwards=false
• 关键词: Approximation; Algorithms; 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.

在过去十五年中，近似算法领域以惊人的速度发展。除了近似算法与实际应用的明显联系之外，另一个机会是利用该领域开发的方法在其他领域取得概念突破。一个突出的例子是与相对较新的算法博弈论领域的自然联系，该领域试图回答新一代分布式系统（包括互联网、P2P 系统、网络和无线系统）提出的问题。最近令人兴奋的工作关于网络编码的研究也与近似算法建立了牢固的联系。此外，这个领域仍然令人兴奋——尽管速度比 1990 年代慢，但仍然可以获得非常基本的见解，并且一些基本问题仍未解决。 PI 的研究涉及两个方面：区域接口的研究以及近似算法中一些尚未解决的基本问题的研究。