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

AF：媒介：协作研究：论组合优化中数学规划的力量

• 批准号: 1407779
• 负责人: James Lee
• 金额: $ 36.74万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1407779&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Power

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.

数学规划是解决组合问题的有力工具。通过将离散任务转化为凸体上的优化问题，将离散任务转化为相关的连续任务。线性规划和半定规划(LP和SDP)是组合优化的重要特例，是组合优化理论和实践的核心工具。这些方法在计算精确解困难的问题的近似最优解方面取得了惊人的成功。虽然已知关于特定松弛族的有效性的非常强的界，但添加少量的变量或约束仍有可能导致解的显著改善。我们建议发展一种理论，在没有任何复杂性理论假设的情况下无条件地捕捉LP和SDP的力量。我们的方法有可能展示一些值得注意的东西：对于许多众所周知的问题，基本的LP或SDP在非常大的一类算法中是最优的。更具体地说，我们提出了一种方法，它可以严格地刻画多项式大小的LP和SDP对于各种组合优化任务的能力。这涉及许多数学和计算机科学领域交叉的深层次问题，最终目的是大大扩展我们对高效计算的理解。数学编程对许多领域都很重要-对于计算机科学和运筹学研究更是如此。这些方法在科学领域的“大数据”分析中的使用也大幅增加。从不同的角度来看，LP和SDP可以被认为是丰富的证明系统，刻画它们的能力是证明复杂性理论中的一个基本问题。因此，拟议研究的结果引起了广大科学家、数学家和实践者的兴趣。