Flexible and Effective Techniques for the Design of Approximation Algorithms

灵活有效的逼近算法设计技术

• 批准号: 288340-2012
• 负责人: Konemann, Jochen
• 金额: $ 3.06万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=594836
• 关键词: Flexible; Effective; Techniques; Design; Approximation

Discrete optimization problems are abundant in everyday life, and arise whenever complex decisions about the efficient distribution of scarce resources have to be made. There is a plethora of such problems, including the timely scheduling of trains in a local transit network, and the optimal layout of wires in the VLSI design phase of a modern chip. In these two examples, and in general, relevant practical instances are often NP-hard, and thus intractable. This proposal focuses on the design of Approximation Algorithms that efficiently compute near-optimal solutions to given optimization problems. Emphasis will be placed on the systematic use of mathematical programming (MP) in the design of such algorithms.

离散优化问题在日常生活中大量存在，并且每当必须做出关于稀缺资源的有效分配的复杂决策时就会出现。这样的问题太多了，包括当地交通网络中列车的及时调度，以及现代芯片VLSI设计阶段的线路优化布局。在这两个例子中，一般来说，相关的实际情况往往是NP难的，因此是棘手的。该建议的重点是设计近似算法，有效地计算近似最优的解决方案，以给定的优化问题。重点将放在系统使用数学规划（MP）在设计这样的算法。