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 vs NP问题的基本理解。该项目旨在开发新的工具和技术，以获得基本优化问题的改进近似算法，包括TSP和约束满足问题。该项目旨在证明稳定多项式的新代数性质，并从代数角度研究图形。这些工具将导致设计一类新的近似算法。这些新的工具出来，这个项目将被纳入下一代课程的近似算法，重点是代数技术。虽然以计算机科学理论为基础，但该项目也将吸引许多来自机器学习和人工智能等应用领域的理论之外的研究生，为跨学科研究奠定基础。