Canada Research Chair in Combinatorial Optimization

加拿大组合优化研究主席

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

我们不断发展的社会每天都面临着许多离散优化问题。例如，协调车队，定位配电中心，以及大规模电路设计中的布线。不幸的是，即使有了庞大的计算集群，我们仍然无法有效地准确解决这些问题。我设计近似算法来找到这些问题的近似最优解。这些都是有效的算法，也绝对保证找到的解决方案在最优值的某个有界误差内。我的工作也弥合了我们对实际使用的整数规划算法和计算理论的理解之间的差距，并可以节省时间，燃料和金钱。