AF: Small: New Perspectives on Mathematical Programming Relaxations

该项目将研究设计有效的物流方法，并为困难的优化问题提供可证明的保证。优化问题出现在许多不同的环境中（例如，为送货卡车找到最佳路线，在社交网络中找到集群等）。我们现在知道，对于许多这样的问题，我们并不期望设计出有效的算法（即在多项式时间内运行），从而产生最优解。近似算法领域开发了原则性的方法来设计用于此类困难优化问题的算法。这个项目将推进我们的数学规划松弛的知识？这是在设计这种近似算法中广泛使用的工具。这里的思想如下：首先，用带有约束的整数变量来表达问题。接下来，通过允许变量取分数值来放松问题。放松的版本可以在多项式时间内精确求解。最后，将小数版本的解映射回整数，同时尽可能保持解的质量。该项目将试图推进我们对这项技术的力量及其在该领域基本问题上的局限性的理解。特别是，PI将调查问题实例中的结构，其中可以通过求解松弛来获得原始问题的精确解，研究基本问题的新松弛，如k均值聚类。PI还将研究以发现图内部的稠密结构为目标的问题以及将图的顶点布置在一条线上的问题的松弛。将根据本项目的研究成果以及该领域的新发展开发研究生和本科生课程的教材。在这个数学规划放松项目中调查的确切恢复问题在理论计算机科学以外的社区中引起了极大的兴趣;这里的新见解有可能影响和影响这些其他社区。本科生将参与项目的适当选择部分，以便在早期阶段将他们暴露于研究。PI将鼓励妇女和少数民族参与这项研究。他将在斯坦福大学组织外展和社区建设活动，利用他过去组织此类活动的经验。这个项目将研究并揭示数学规划松弛在各种设置中的组合优化问题。该项目的主要目标是：1。通过数学规划的精确恢复：调查和理解数学规划松弛返回整数解的现象。PI将这个新的透镜应用于线性规划（LP）和半定规划（SDP）松弛的几个问题。具体来说，PI将研究SDP松弛，用于计算点集上的变换不变度量，并解决相关随机图模型的近似图同构（最近在社交网络的去匿名化和隐私研究中引入）。聚类问题：研究最近引入的用于k-means目标的SDP松弛，以获得更好的最差情况近似因子。PI还将研究这种松弛在聚类点的随机模型上的性能，这些模型更好地代表了实践中的实例。Denmark子图：研究超图推广的k-denominator-subgraph问题和一个密切的变化，最小的m-edge-subgraph，了解最佳的近似因子可实现的，以及是否自然种植的随机超图的实例建议一个自然的限制，有效的近似算法。PI还将研究denominator子图的下界，以理解预测为问题最难的种植实例的拉瑟尔层次结构。布局问题：PI将研究两个不同的经典优化问题，包括将（无）有向图的顶点映射到直线：最小化（a）割宽和（B）反馈弧集，以改善最差情况下的近似因子。对于cutwidth，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.