Design, analysis and Theory of Algorithms

算法设计、分析与理论

• 批准号: RGPIN-2017-06551
• 负责人: Borodin, Allan
• 金额: $ 3.64万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634811
• 关键词: Design; analysis; Theory; Algorithms

This proposal concerns a number of different research areas. However, my recent research interests are often motivated by the question as to what can and cannot be computed by ``conceptually simple algorithms''. In this regard, my primary interest concerns conceptually simple approximation algorithms for combinatorial optimization problems. More specifically, I am studying various forms and extensions of online and greedy algorithms, primal dual algorithms, dynamic programming algorithms, local algorithms, and local search. And most recently, I have been concerned with domains where rather naive randomization can often outperform more ``principled'' and sophisticated deterministic algorithms. As examples, we can ask, what is the simplest deterministic one pass algorithm that can match or surpass the 3/4 approximation ratio achieved by various algorithms for the Max-Sat problem and the same question as to exceeding the 1-1/e approximation for online bipartite matching. In particular, I am studying parallel and multi-pass online and greedy algorithms. It has recently been shown that such algorithms can be sometimes be derived from randomized algorithms. However, so far there are only a couple of

这项建议涉及若干不同的研究领域。然而，我最近的研究兴趣往往是由问题的动机，什么可以和不能计算的“概念上简单的算法”。在这方面，我的主要兴趣关注概念上简单的组合优化问题的近似算法。更具体地说，我正在研究在线和贪婪算法，原始对偶算法，动态规划算法，局部算法和局部搜索的各种形式和扩展。最近，我一直在关注一些领域，在这些领域中，相当天真的随机化往往比更“有原则”和复杂的确定性算法更好。作为例子，我们可以问，什么是最简单的确定性一遍算法，可以匹配或超过3/4近似比实现的各种算法的最大卫星问题和相同的问题，以超过1-1/e近似在线二分匹配。特别是，我正在研究并行和多通道在线和贪婪算法。最近已经表明，这样的算法有时可以从随机算法中推导出来。然而，到目前为止，只有几个