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可以被认为是丰富的证明系统，表征它们的能力是证明复杂性理论中的一个基本问题。因此，提议的研究结果引起了广大科学家、数学家和实践者的兴趣。