The vast majority of planning or design tasks involves an optimization problem, seeking to either minimize the cost of the proposed solution, or maximize its efficiency or payoff. Often, the goal would be the identification of the optimal solution from a set of finite many discrete options (combinatorial optimization). Unfortunately, an exact solution for the overwhelming majority of optimization problems turns out to be computationally intractable. To cope with intractability, one often settles for algorithms that provably approximate the optimal solution. The following question stems naturally from the notion of approximation: For a given combinatorial optimization problem, what is the best approximation to the optimal solution that can be efficiently computed?
There are two facets to answering the above question: designing approximation algorithms and showing that no efficient algorithm can provide a better approximation guarantee (hardness result). The convergence of these two seemingly different facets has been one of the most exciting developments in theoretical computer science in recent years. This project would involve the design of improved approximation algorithms as well as showing that these algorithms are essentially optimal. Although the design of approximation algorithms is a vast area of research, the main tool underlying an overwhelming majority of existing approximation algorithms is a convex optimization technique such as linear or semidefinite programming. Existing algorithmic techniques have hit upon a common barrier on a large number of fundamental combinatorial optimization problems, a barrier that is encapsulated by the tantalizing "Unique Games Conjecture (UGC)." Therefore the study of approximability is at a very exciting juncture. On one hand, an affirmation of the UGC would resolve long standing open questions , demonstrate an underlying unity in combinatorial optimization problems, and, more importantly, show that the simplest semidefinite programs yield the best approximations. On the other hand, disproving the UGC would lead to new algorithmic techniques that will eventually lead to better approximation algorithms.
The PI proposes a set of research questions involving both design of approximation algorithms and hardness of approximation results. Broadly speaking, the project has the following four research themes:
1) Understand the power of semidefinite programming hierarchies via the design of new algorithms and constructions of integrality gap examples.
2) Extend the emerging framework of approximability under the UGC to a larger class of combinatorial optimization problems.
3) Develop technical machinery and gadgets to show unconditionally some of the hardness results based on the UGC, making progress towards its resolution.
4) Apply the analytic tools developed in hardness of approximation to other branches of theoretical computer science, such as the study of exact algorithms for constraint satisfaction problems.
This research necessarily draws upon tools from various theoretical disciplines such as coding theory, property testing, computational learning, derandomization and discrete harmonic analysis. The research has a strong potential for broader impact in terms of scientific workshops, developement of graduate courses, lecture notes and survey articles on the latest research in approximation, promoting undergraduate research, and advising Ph.D students.
