Canada Research Chair in Combinatorial Optimization

加拿大组合优化研究主席

• 批准号: 1000230198-2014
• 负责人: Friggstad, Zachary
• 金额: $ 8.74万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Canada Research Chairs
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=651201
• 关键词: Canada; Research; Chair; Combinatorial; Optimization

Our ever-growing society is faced with a number of discrete optimization problems on a daily basis. Examples are coordinating fleets of vehicles, locating distribution centres, and routing wires in large-scale circuit design. Unfortunately, even with our massive computing clusters, we are still unable to efficiently solve these problems exactly. I devise approximation algorithms to find near-optimum solutions to these problems. These are efficient heuristics that also come with an absolute guarantee that the solutions found are within some bounded error of the optimum. My work also bridges the gap between our understanding of integer programming heuristics used in practice and the theory of computing, and can lead to savings in time, fuel, and money.*

我们不断发展的社会每天都面临许多离散的优化问题。例如，在大规模电路设计中协调车辆舰队，定位配电中心和路由电线。不幸的是，即使有了我们庞大的计算簇，我们仍然无法有效地准确地解决这些问题。我设计了近似算法，以找到针对这些问题的接近最短的解决方案。这些是有效的启发式方法，也可以绝对保证找到的解决方案在最佳的某些有界误差范围内。我的工作还弥合了我们对实践中使用的整数编程启发式方法的理解与计算理论之间的差距，并且可以节省时间，燃料和金钱。