CAREER: Metric Geometry Techniques for Approximation Algorithms

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

Combinatorial optimization problems are of great importance to numerous applications. They arise in operations research, machine learning, VLSI design, computational biology and many other areas. Many optimization problems however are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. It is natural therefore to look for approximation algorithms, efficient algorithms that find only approximate solutions. Design and analysis of approximation algorithms is a very active research area. Various approaches for solving combinatorial optimization problems have appeared in the last three decades. However, despite significant progress, many important problems are still open. This research project aims to advance the application of metric geometry techniques for solving combinatorial optimization problems, investigate new methods for designing approximation algorithms, and develop tools for analyzing the performance of approximation algorithms on real-life instances. This research project will be both theoretically important and practically relevant and it will lead to development of approximation algorithms for important applied problems that occur in many fields of science and engineering. Specifically, the PI will work on the following problems.* Traditionally most research has focused on analyzing the worst case performance of approximation algorithms. However, practitioners observe that instances of combinatorial optimization problems that arise in practice are often not as hard as worst case instances. The PI will study semi-random models for various combinatorial optimization problems, and develop approximation algorithms that perform well on semi-random instances. This can perhaps explain what we see in practice.* Recent research in the hardness of approximation initiated by Khot identified Unique Games Problem as a combinatorial obstacle to the development of approximation algorithms for many problems. The PI will study algorithmic techniques for solving the Unique Games Problem.* The PI will study lift-and-project hierarchies of linear programming (LP) and semi-definite programming (SDP) relaxations, analyze their integrality gaps, and design subexponential approximation algorithms that use these hierarchies.* There is a close connection between some areas of theoretical computer science and pure mathematics. To settle down some problems in combinatorial optimization, we need to resolve closely connected open problems in analysis. The PI will explore several problems with deep ties to computer science and mathematics.