AF: Medium: Collaborative Research: On the Power of Mathematical Programming in Combinatorial Optimization

数学规划是求解组合问题的有力工具。 通过将离散任务转换为凸体上的优化，将其转换为相关的连续任务。 线性和半定规划（LP和SDP）是重要的特例，是组合优化理论和实践中的核心工具。这些方法已经取得了惊人的成功，在计算近似的最优解的问题，找到精确的解决方案是计算targeted.While有非常强大的边界上的特定家庭的弛豫的功效已知，它仍然有可能，添加少量的变量或约束可能会导致大幅改善的解决方案。 我们提出了一个理论的发展，无条件地捕捉LP和SDP的权力，没有任何复杂性理论的假设。 我们的方法有可能显示出一些显着的：对于许多众所周知的问题，基本的LP或SDP是最佳的一类非常大的算法。 更具体地说，我们提出了一种方法，可以严格表征多项式大小的LP和SDP的各种组合优化任务的权力。 这涉及到数学和计算机科学许多领域交叉的深层次问题，其最终目标是显著扩展我们对有效计算的理解。数学编程对许多领域都非常重要-尤其是计算机科学和运筹学。 这些方法在科学领域的“大数据”分析中的使用也急剧增加。 从另一个角度来看，LP和SDP可以被认为是丰富的证明系统，刻画它们的能力是证明复杂性理论中的一个基本问题。因此，拟议研究的结果是感兴趣的科学家，数学家和从业者的广泛社区。

Mathematical programming is a powerful tool for attacking combinatorial problems. One transforms a discrete task into a related continuous one by casting it as optimization over a convex body. Linear and semi-definite programming (LP and SDP) form important special cases and are central tools in the theory and practice of combinatorial optimization. These approaches have achieved spectacular success in computing approximately optimal solutions for problems where finding exact solutions is computationally intractable.While there are very strong bounds known on the efficacy of particular families of relaxations, it remains possible that adding a small number of variables or constraints could lead to drastically improved solutions. We propose the development of a theory to unconditionally capture the power of LPs and SDPs without any complexity-theoretic assumptions. Our approach has the potential to show something remarkable: For many well-known problems, the basic LP or SDP is optimal among a very large class of algorithms. More concretely, we suggest a method that could rigorously characterize the power of polynomial-size LPs and SDPs for a variety of combinatorial optimization tasks. This involves deep issues at the intersection of many areas of mathematics and computer science, with the ultimate goal of significantly extending our understanding of efficient computation.Mathematical programming is of major importance to many fields---this is especially true for computer science and operations research. These methods have also seen dramatically increasing use in the analysis of "big data" from across the scientific spectrum. From a different perspective, LPs and SDPs can be thought of as rich proof systems, and characterizing their power is a basic problem in the theory of proof complexity. Thus the outcomes of the proposed research are of interest to a broad community of scientists, mathematicians, and practitioners.