CAREER: Pursuing New Tools for Approximation Algorithms

许多大型工业现在都在使用复杂的算法来解决各种基本优化问题。例如，亚马逊使用旅行推销员问题（TSP）的一个变体，即为亚马逊生鲜卡车安排路线的车辆路线问题。优步解决了TSP的一个变体，以路由其共享乘车服务。包括Facebook和b谷歌+在内的许多社交网络都为其社交目标任务解决了各种约束满意度问题。这些优化问题具有普遍的适用性，但它们在计算上具有挑战性，因为许多问题已知是np困难的。这意味着在标准假设下，它们不能通过在合理时间内终止的算法得到最优解。近似算法领域试图开发有效的算法来找到接近最优解。这些近似算法在现实世界中有许多应用。该项目将推进最先进的近似算法，这不仅对工业产生影响，而且有助于我们对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.