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

点击翻译按钮获取中文摘要

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.