The project will study methods for designing efficient heuristics with provable guarantees for hard optimization problems. Optimization problems arise in many different contexts (e.g. finding the best routes for delivery trucks, finding clusters in a social network, etc). We now know that for many such problems, we do not expect to design algorithms that are efficient (i.e. run in polynomial time) that produce optimal solutions. The field of approximation algorithms develops principled methods to design algorithms for such hard optimization problems. This project will advance our knowledge of mathematical programming relaxations ? a widely used tool in the design of such approximation algorithms. The idea here is as follows: First, express the problem in terms of integer variables with constraints on them. Next relax the problem by allowing variables to take on fractional values. The relaxed version can be solved exactly in polynomial time. Finally, map solutions to the fractional version back to integers, while attempting to maintain the quality of the solution as far as possible. The project will attempt to advance our understanding of the power of this technique and its limitations for fundamental problems in the field. In particular, the PI will investigate structure in problem instances where exact solutions to the original problem can be obtained from solving the relaxation, study new relaxations for basic problems such as k-means clustering. The PI will also study relaxations for problems where the goal is find a dense structure inside a graph and problems involving laying out the vertices of a graph on a line.
Course materials for graduate and undergraduate courses will be developed distilling research results from this project, as well as new developments in the field. The exact recovery questions investigated in this project for mathematical programming relaxations are of great interest in communities other than theoretical computer science; new insights here have the potential to influence and impact these other communities. Undergraduates will be involved in appropriately chosen pieces of the project so as to expose them to research at an early stage. The PI will encourage the participation of women and minorities in this research. He will organize outreach and community building activities at Stanford, leveraging his experience with organizing such activities in the past.
This project will study and shed new light on mathematical programming relaxations for hard combinatorial optimization problems in various settings. The broad goals of this project are:
1. Exact recovery via mathematical programming: Investigate and understand the phenomenon of mathematical programming relaxations returning integer solutions. The PI will apply this new lens to linear programming (LP) and semidefinite programming (SDP) relaxations for several problems. Specifically, the PI will study SDP relaxations for computing transformation invariant metrics on sets of points and solving approximate graph isomorphism for correlated random graph models (introduced recently in the study of de-anonymization and privacy in social networks).
2. Clustering problems: Investigate a recently introduced SDP relaxation for the k-means objective to obtain a better worst case approximation factor. The PI will also investigate the performance of this relaxation on random models of clustered points that better represent instances in practice.
3. Densest subgraph: Investigate hypergraph generalizations of the k-densest-subgraph problem and a close variant, the smallest-m-edge-subgraph, to understand the best approximation factor achievable and whether natural planted instances of random hypergraphs suggest a natural limit for efficient approximation algorithms. The PI will also study lower bounds for densest subgraph, to understand the Lasserre hierarchy for planted instances that are predicted to be the hardest for the problem.
4. Layout problems: The PI will study two different classical optimization problems involving mapping the vertices of a (un)directed graph to a line: minimizing (a) Cutwidth, and (b) Feedback Arc Set, to improve the worst case approximation factors. For cutwidth, the PI will investigate a new mathematical programming relaxation motivated by lift-and-project hierarchies. For Feedback Arc Set, the PI will study a new semidefinite programming relaxation.
5. Constructive Discrepancy: Recent advances in designing efficient algorithms for minimizing discrepancy suggest that new breakthroughs are possible. A recent result builds on a breakthrough on the Kadison-Singer problem to show that the integrality gap of a natural relaxation for Asymmetric Traveling Salesman is small. The PI will investigate whether this existential result can be made algorithmic. The PI will also study the Beck-Fiala and Komlos conjectures, where efficient algorithms can lead to new progress.
