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

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

• 批准号: 1408643
• 负责人: Prasad Raghavendra
• 金额: $ 36.64万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1408643&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可以被认为是丰富的证明系统，而表征它们的能力是证明复杂性理论中的一个基本问题。因此，所提出的研究结果引起了广大科学家、数学家和从业者的兴趣。