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

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

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.