CAREER: Pursuing New Tools for Approximation Algorithms

许多大型工业现在都在使用复杂的算法来解决基本优化问题的各种变体。例如，亚马逊使用旅行商问题(TSP)的变体来为Amazon-Fresh卡车提供路线，该问题被称为车辆路线问题。优步解决了TSP的一个变种，以确定其拼车服务的路线。包括Facebook和谷歌在内的许多社交网络都为他们的社交目标任务解决了各种约束满足感问题。这些优化问题具有普遍的适用性，但它们在计算上具有挑战性，因为许多问题都是已知的NP-Hard。这意味着，在标准假设下，它们不能通过在合理时间内终止的算法以最优方式解决。近似算法领域试图开发找到接近最优解的高效算法。这些近似算法在现实世界中有很多应用。该项目将推进最先进的近似算法，这不仅将对工业产生影响，而且有助于我们对计算机科学的核心问题P与NP问题的基本理解。本项目旨在开发新的工具和技术来获得基本优化问题的改进近似算法，包括TSP和约束满足问题。该项目旨在证明稳定多项式的新的代数性质，并用它们从代数的角度研究图。这些工具将导致设计一类新的近似算法。这些从这个项目中产生的新工具将被整合到专注于代数技术的下一代近似算法课程中。尽管该项目以计算机科学理论为基础，但也将吸引许多来自机器学习和人工智能等应用领域的理论以外的研究生，为跨学科研究奠定基础。

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.