AF: Small: Parallels in Approximability of Discrete and Continuous Optimization Problems

AF：小：离散和连续优化问题的近似性的相似性

基本信息

批准号：
1816372
负责人：
Madhur Tulsiani
金额：
$ 49.72万
依托单位：
Toyota Technological Institute at Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816372&HistoricalAwards=false
关键词：
AF Small Parallels Approximability Discrete

项目摘要

Optimization problems arise naturally in many areas such as scheduling, artificial intelligence, software engineering, control of robotic systems, statistics and machine learning. Many of these problems require too long to solve exactly - a common approach for dealing with this has been to design techniques which can efficiently find approximate solutions that are 'good enough' for the task at hand. The study of what approximations are best possible, as well as methods for achieving them, has also led to many new ideas in theoretical computer science, leading to a rich mathematical theory. This project considers several such problems (arising in different areas) which represent challenges to our current understanding. The goal of the project is to develop unified techniques for solving and analyzing them. The project includes several opportunities for training and mentoring of graduate and undergraduate students. Another aim of the project is to develop a collaborative forum for theoretical computer science students in the Chicago area, which can be used to discuss technical ideas and develop expository material.This project considers various problems in discrete and continuous optimization, which represent bottlenecks for algorithmic techniques for designing approximation algorithms, as well as for techniques proving hardness of approximation. The difficulty of understanding many of these problems arises from the fact that many of them only impose a relatively weak global constraint on the solutions, which is hard to exploit algorithmically and also not amenable to techniques for proving inapproximability. The project considers several continuous optimization problems which offer an ideal testbed for the development of new algorithmic techniques, while still capturing the bottlenecks in proving inapproximability of related discrete problems. The aim of this project is to examine such problems from the following perspectives: (1) average-case hardness and lower bounds for the Sum-of-Squares hierarchy of convex relaxations; (2) techniques and barriers for proving inapproximability; and (3) conditions under which good approximations are achievable.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

优化问题自然出现在许多领域，例如调度、人工智能、软件工程、机器人系统控制、统计和机器学习。其中许多问题需要太长时间才能准确解决 - 处理此问题的常见方法是设计能够有效找到对于当前任务“足够好”的近似解决方案的技术。对什么是最好的近似以及实现它们的方法的研究也引发了理论计算机科学的许多新思想，从而产生了丰富的数学理论。该项目考虑了几个此类问题（出现在不同领域），这些问题对我们当前的理解提出了挑战。该项目的目标是开发解决和分析这些问题的统一技术。该项目包括多个培训和指导研究生和本科生的机会。该项目的另一个目标是为芝加哥地区的理论计算机科学学生建立一个协作论坛，可用于讨论技术思想和开发说明材料。该项目考虑了离散和连续优化中的各种问题，这些问题代表了算法的瓶颈设计近似算法的技术，以及证明近似硬度的技术。理解这些问题中的许多问题的困难在于，许多问题仅对解决方案施加相对较弱的全局约束，这很难通过算法来利用，也不适合证明不可近似性的技术。该项目考虑了几个连续优化问题，为新算法技术的开发提供了理想的测试平台，同时仍然捕获了证明相关离散问题不可近似性的瓶颈。该项目的目的是从以下角度研究此类问题：（1）平均情况硬度和凸松弛平方和层次结构的下界； (2) 证明不可近似性的技术和障碍； (3) 可以实现良好近似值的条件。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Concentration of polynomial random matrices via Efron-Stein inequalities

通过 Efron-Stein 不等式进行多项式随机矩阵的集中

DOI：
发表时间：
2023-01
期刊：
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Rajendran, Goutham;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem

将 Grothendieck 问题的 NP 难度与 Little-Grothendieck 问题分开