Computational problems have become pervasive in all fields of science where huge amounts of data have to be processed efficiently. For computationally hard problems where computing the exact optimum solution is intractable, the next best option is to design efficient approximation algorithms that find solutions that are provably close to the optimum. In this project, the PI and the supported graduate student will design such approximation algorithms based on the still poorly understood Lasserre semidefinite programming hierarchy. The goal is to provide better algorithms for several key problems that are studied in combinatorial optimization. Practical applications of approximation algorithms can be found in many areas of science and industry. Moreover, this proposal includes the integration of research and teaching by means of graduate courses that cover the Lasserre hierarchy in a manner accessible for graduate students outside of theoretical computer science.
More concretely, the goal is to develop approximation algorithms based on the Lasserre SDP for outstanding unsolved problems like Directed Steiner Tree, Graph Coloring, Unrelated Machine Scheduling and Unique Games. In particular this means designing new rounding schemes to extract valid integral solutions and developing the analytical techniques needed to study their effectiveness. A key ingredient will be the development of a better understanding of the vector embeddings for higher moments that are provided by the Lasserre SDP.
Keywords: Approximation algorithms; Semidefinite programs; Integrality gaps; Lasserre hierarchy
