Improved Mathematical Programming Techniques for Approximation Algorithms

改进近似算法的数学编程技术

• 批准号: RGPIN-2015-06496
• 负责人: Friggstad, Zachary
• 金额: $ 1.68万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634899
• 关键词: Improved; Mathematical; Programming; Techniques; Approximation

A striking number of problems in discrete optimization are, unfortunately, computationally intractable. These problems stem from issues faced by our complex society: coordinating vehicles in a transportation network, compiling code to create efficient executable programs, determining placements of fire or ambulance stations to improve response time. More precisely, many such problems are NP-hard meaning we do not have, nor do we expect, any efficient algorithms to solve these problems optimally. To cope with this difficulty, we focus on devising efficient algorithms that find near-optimum solutions.

不幸的是，在离散优化中有大量的问题在计算上是棘手的。这些问题源于我们复杂社会所面临的问题：在运输网络中协调车辆，编译代码以创建有效的可执行程序，确定放置或救护车站的位置以改善响应时间。更确切地说，许多这样的问题都是NP顽强的，这意味着我们没有，也没有期望任何有效算法可以最佳地解决这些问题。为了应对这一难度，我们专注于设计有效的算法，这些算法几乎可以找到最短的解决方案。