Algorithmic discrete mathematics with applications

算法离散数学及其应用

• 批准号: 137764-2011
• 负责人: Hayward, Ryan
• 金额: $ 1.75万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569295
• 关键词: Algorithmic; discrete; mathematics; applications

I am interested in algorithms related to two recent developments. In 2002, Chudnovsky et al. proved the Strong Perfect Graph Theorem, the biggest open problem in graph theory since Appel and Haken's 1976 proof of the Four Color Theorem in 1976. Related to this recent monumental result is an intriguing open problem: given a graph satisfying the conditions of the theorem, is there an efficient simple (so, not using the complicated mathematics of the ellipsoid method) way to find a largest clique ? For this problem, I am seeing if I can solve this problem on a smaller class of graphs. In 2006, the world learned the strength of the computer Go programs Crazystone by Coulom and MoGo by Gelly. Since then, there has been a revolution in computer Go that has spilled into many areas of computer science, with applications as wide ranging as finding suitable schedules for multi-plant power generation systems. Underlying this revolution is Monte Carlo tree search, a new randomized method for performing a search in a huge solution space. For this problem, I am experimenting with these ideas on a simpler game than Go.

我感兴趣的算法与两个最近的发展。 2002年，Chudnovsky等人证明了强完美图定理，这是自阿佩尔和哈肯在1976年证明四色定理以来图论中最大的开放问题。 与这一最近的重大成果相关的是一个有趣的开放问题：给定一个图， 满足定理的条件，是否有一个有效的简单（因此，不使用复杂的数学椭球方法）的方法来找到一个最大的团？ 对于这个问题，我想看看我是否能在一个更小的图类上解决这个问题。 2006年，世界了解了计算机围棋程序Crazystone的力量 Gelly的MoGo 从那时起，计算机围棋的革命已经蔓延到计算机科学的许多领域，应用范围广泛，为多工厂发电系统找到合适的时间表。 这场革命的基础是蒙特卡洛树搜索，一种新的 在一个巨大的解决方案空间中执行搜索的随机方法。 对于这个问题，我正在一个比围棋更简单的游戏上试验这些想法。