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 提供的更高矩的向量嵌入。关键词：近似算法；半定规划；完整性差距；拉塞尔层次结构

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Tale of Santa Claus, Hypergraphs and Matroids

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

DOI：
10.1137/1.9781611975994.167
发表时间：
2020-01
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Davies, Sami;Rothvoss, Thomas Rothvoss;Zhang, Yihao
通讯作者：
Zhang, Yihao

Scheduling with Communication Delays via LP Hierarchies and Clustering

通过 LP 层次结构和集群进行通信延迟调度

DOI：
10.1109/focs46700.2020.00081
发表时间：
2020-04-21
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
0
作者：
Sami Davies;Janardhan Kulkarni;T. Rothvoss;Jakub Tarnawski;Yihao Zhang
通讯作者：
Yihao Zhang

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

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

DOI：
发表时间：
2021-01
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Davies, Sami;Kulkarni, Janardhan;Rothvoss, Thomas;Tarnawski, Jakub;Zhang, Yihao
通讯作者：
Zhang, Yihao

The Vector Balancing Constant for Zonotopes

区域位点的矢量平衡常数