CAREER: Pursuing New Tools for Approximation Algorithms

职业：追求近似算法的新工具

• 批准号: 1552097
• 负责人: Shayan Gharan
• 金额: $ 40万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-03-01 至 2022-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552097&HistoricalAwards=false
• 关键词: CAREER; Pursuing; New; Tools; Approximation

Many of the large-scale industries are now employing sophisticated algorithms to solve variants of fundamental optimization problems. For example, Amazon uses a variant of the Traveling Salesman Problem (TSP) known as the vehicle routing problem for routing Amazon-Fresh Trucks. Uber solves a variant of TSP to route its shared-ride services. Many of the social networks including Facebook and Google+ solve variants of constraints satisfaction problems for their social targeting tasks. These optimization problems have ubiquitous applicability but they are computationally challenging in the sense that many are known to be NP-hard. This means that under standard assumptions they cannot be solved optimally by algorithms which terminate in reasonable time. The field of approximation algorithms attempts to develop efficient algorithms that find solutions close to the optimum. These approximation algorithms have found many applications in the real world. The project will advance state-of-the-art in approximation algorithms which will not only have impact on industry but also contribute to our fundamental understanding of P vs NP issue, which is at the core of computer science.This project aims to develop new tools and techniques to obtain improved approximation algorithms for fundamental optimization problems, including the TSP and Constraint Satisfaction problems. The project intends to prove new algebraic properties of stable polynomials and use them to study graphs from an algebraic point of view. These tools will lead to design a new class of approximation algorithms. These new tools coming out of this project will be incorporated in the next generation of courses in approximation algorithms that focus on algebraic techniques. Although grounded in computer science theory, the project will also attract many graduate students outside of theory from applied fields like machine learning and artificial intelligence forming basis for interdisciplinary research.

许多大型行业现在都采用复杂的算法来解决基本优化问题的变体。例如，亚马逊使用旅行商问题 (TSP) 的变体（称为车辆路径问题）来为亚马逊生鲜卡车进行路径选择。 Uber 解决了 TSP 的变体来路由其共享乘车服务。包括 Facebook 和 Google+ 在内的许多社交网络都解决了其社交定位任务的各种约束满足问题。这些优化问题具有普遍的适用性，但它们在计算上具有挑战性，因为许多问题都被认为是 NP 困难的。这意味着在标准假设下，它们无法通过在合理时间终止的算法来最佳解决。近似算法领域试图开发有效的算法来找到接近最优的解决方案。这些近似算法在现实世界中得到了许多应用。该项目将推进最先进的近似算法，这不仅会对行业产生影响，而且有助于我们对 P 与 NP 问题的基本理解，这是计算机科学的核心。该项目旨在开发新的为基本优化问题（包括 TSP 和约束满足问题）获得改进的近似算法的工具和技术。该项目旨在证明稳定多项式的新代数性质，并用它们从代数的角度研究图。这些工具将导致设计一类新的近似算法。该项目产生的这些新工具将被纳入下一代以代数技术为重点的近似算法课程中。尽管该项目以计算机科学理论为基础，但也将吸引许多来自机器学习和人工智能等应用领域理论之外的研究生，为跨学科研究奠定基础。