CAREER: Approximation Algorithms via SDP hierarchies

计算问题已经普遍存在于所有需要有效处理大量数据的科学领域。对于计算困难的问题，计算精确的最优解是棘手的，下一个最佳选择是设计有效的近似算法，找到可证明接近最优的解决方案。在这个项目中，PI和支持的研究生将设计这样的近似算法的基础上仍然知之甚少的拉瑟尔半定规划层次。目标是为组合优化中的几个关键问题提供更好的算法。近似算法的实际应用可以在科学和工业的许多领域中找到。此外，该提案还包括通过研究生课程整合研究和教学，这些课程以理论计算机科学之外的研究生可以访问的方式涵盖拉瑟尔层次结构。更具体地说，我们的目标是开发近似算法的基础上拉瑟尔SDP的突出未解决的问题，如有向斯坦纳树，图着色，无关的机器调度和独特的游戏。特别是，这意味着设计新的舍入方案，以提取有效的积分解决方案，并开发研究其有效性所需的分析技术。一个关键的因素将是更好地理解矢量嵌入的更高的时刻，由拉瑟尔SDP提供的发展。关键词：逼近算法;半定规划;积分间隙;拉瑟尔层次

Computational problems have become pervasive in all fields of science where huge amounts of data have to be processed efficiently. For computationally hard problems where computing the exact optimum solution is intractable, the next best option is to design efficient approximation algorithms that find solutions that are provably close to the optimum. In this project, the PI and the supported graduate student will design such approximation algorithms based on the still poorly understood Lasserre semidefinite programming hierarchy. The goal is to provide better algorithms for several key problems that are studied in combinatorial optimization. Practical applications of approximation algorithms can be found in many areas of science and industry. Moreover, this proposal includes the integration of research and teaching by means of graduate courses that cover the Lasserre hierarchy in a manner accessible for graduate students outside of theoretical computer science. More concretely, the goal is to develop approximation algorithms based on the Lasserre SDP for outstanding unsolved problems like Directed Steiner Tree, Graph Coloring, Unrelated Machine Scheduling and Unique Games. In particular this means designing new rounding schemes to extract valid integral solutions and developing the analytical techniques needed to study their effectiveness. A key ingredient will be the development of a better understanding of the vector embeddings for higher moments that are provided by the Lasserre SDP. Keywords: Approximation algorithms; Semidefinite programs; Integrality gaps; Lasserre hierarchy