CAREER: Approximation Algorithms via SDP hierarchies

职业：通过 SDP 层次结构的近似算法

• 批准号: 1651861
• 负责人: Thomas Rothvoss
• 金额: $ 52.22万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-02-01 至 2024-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1651861&HistoricalAwards=false
• 关键词: CAREER; Approximation; Algorithms; via; 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

在科学的各个领域，计算问题已经变得无处不在，在这些领域中，海量数据必须得到有效处理。对于难以计算精确最优解的问题，下一个最好的选择是设计有效的近似算法，找到可证明接近最优解的解。在这个项目中，PI和被支持的研究生将基于仍然鲜为人知的Lasserre半定规划体系来设计这样的近似算法。其目的是为组合优化中研究的几个关键问题提供更好的算法。近似算法的实际应用可以在科学和工业的许多领域找到。此外，这项建议包括通过研究生课程将研究和教学结合起来，这些课程涵盖拉瑟尔等级制度，研究生可以在理论计算机科学之外的方式获得这些课程。更具体地说，目标是开发基于Lasserre SDP的近似算法，用于解决未解决的突出问题，如有向Steiner树、图着色、无关机器调度和唯一博弈。特别是，这意味着设计新的舍入方案以提取有效的积分解，并开发研究其有效性所需的分析技术。一个关键因素将是更好地理解Lasserre SDP提供的高阶矩的矢量嵌入。关键词：逼近算法；半定程序；完整性间隙；拉瑟尔族

项目成果

Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines

通过 LP 层次结构和集群进行通信延迟调度 II：相关机器上的加权完成时间

• 发表时间: 2021
• 期刊: Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Davies, Sami;Kulkarni, Janardhan;Rothvoss, Thomas;Tarnawski, Jakub;Zhang, Yihao
• 通讯作者: Zhang, Yihao

Linear Size Sparsifier and the Geometry of the Operator Norm Ball

线性尺寸稀疏器和算子规范球的几何形状

• DOI: 10.1137/1.9781611975994.143
• 发表时间: 2020
• 期刊: Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Reis, Victor;Rothvoss, Thomas
• 通讯作者: Rothvoss, Thomas

The Vector Balancing Constant for Zonotopes

区域位点的矢量平衡常数

• DOI: 10.1109/focs57990.2023.00077
• 发表时间: 2023
• 期刊: IEEE
• 作者: Bozzai, Rainie;Reis, Victor;Rothvoss, Thomas
• 通讯作者: Rothvoss, Thomas

A Tale of Santa Claus, Hypergraphs and Matroids

圣诞老人、超图和拟阵的故事

• DOI: 10.1137/1.9781611975994.167
• 发表时间: 2020
• 期刊: Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Davies, Sami;Rothvoss, Thomas Rothvoss;Zhang, Yihao
• 通讯作者: Zhang, Yihao

Scheduling with Communication Delays via LP Hierarchies and Clustering

• DOI: 10.1109/focs46700.2020.00081
• 发表时间: 2020-04
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Sami Davies;Janardhan Kulkarni;T. Rothvoss;Jakub Tarnawski;Yihao Zhang