AF: Small: New Perspectives on Mathematical Programming Relaxations

该项目将研究设计具有可证明保证的有效启发式方法的方法。优化问题出现在许多不同的环境中（例如，为送货卡车找到最佳路线，在社交网络中找到集群，等等）。我们现在知道，对于许多这样的问题，我们并不期望设计出能够产生最优解的高效算法（即在多项式时间内运行）。近似算法领域发展了原则性的方法来设计这种困难的优化问题的算法。这个项目将提高我们对数学规划松弛的认识。在这种近似算法的设计中广泛使用的工具。这里的思想如下：首先，用带有约束的整数变量来表达问题。接下来，通过允许变量取小数值来简化问题。松弛版本可以在多项式时间内精确求解。最后，将小数版本的解映射回整数，同时尽可能地保持解的质量。该项目将试图促进我们对该技术的力量及其在该领域基本问题上的局限性的理解。特别是，PI将研究问题实例中的结构，其中可以通过求解松弛得到原始问题的精确解，研究k-means聚类等基本问题的新松弛。PI也将研究松弛问题，目标是在图中找到一个密集的结构，以及涉及在一条线上布置图的顶点的问题。研究生和本科课程的课程材料将从这个项目中提取研究成果，以及该领域的新发展。在这个项目中，数学规划松弛的精确恢复问题在理论计算机科学以外的社区中引起了极大的兴趣；这里的新见解有可能影响和影响其他社区。本科生将参与适当选择的项目片段，以便他们在早期阶段接触研究。PI将鼓励妇女和少数民族参与这项研究。他将在斯坦福大学组织外展和社区建设活动，利用他过去组织此类活动的经验。该项目将研究并揭示在各种环境下的难组合优化问题的数学规划松弛。这个项目的主要目标是：1。通过数学规划精确恢复：调查和理解数学规划松弛返回整数解的现象。PI将把这种新透镜应用于线性规划（LP）和半定规划（SDP）松弛的几个问题。具体来说，PI将研究用于计算点集合上的变换不变度量和求解相关随机图模型的近似图同构的SDP松弛（最近在社交网络中的去匿名化和隐私研究中引入）。聚类问题：研究最近为k-means目标引入的SDP松弛，以获得更好的最坏情况近似因子。PI还将研究这种松弛在实践中更好地代表实例的聚类点随机模型上的性能。最密集子图：研究k-最密集子图问题的超图推广和一个相近的变体，最小m边子图，以了解可实现的最佳近似因子，以及随机超图的自然种植实例是否为有效的近似算法提供了自然极限。PI还将研究最密集子图的下界，以了解预测最难解决问题的种植实例的Lasserre层次结构。布局问题：PI将研究两个不同的经典优化问题，涉及将（非）有向图的顶点映射到一条线上：最小化(a)切面宽度，和(b)反馈弧集，以改善最坏情况的近似因子。对于宽度，PI将研究一种由升降机和项目层次结构驱动的新的数学规划松弛。对于反馈弧集，PI将研究一种新的半定规划松弛。建设性差异：最近在设计有效算法以最小化差异方面的进展表明，新的突破是可能的。最近的一个结果建立在对Kadison-Singer问题的突破上，证明了非对称旅行推销员的自然松弛的完整性间隙很小。PI将调查这个存在的结果是否可以通过算法来实现。PI还将研究Beck-Fiala和Komlos猜想，在这些猜想中，高效的算法可以带来新的进展。

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.