Design, analysis and Theory of Algorithms

算法设计、分析与理论

• 批准号: RGPIN-2017-06551
• 负责人: Borodin, Allan
• 金额: $ 1.46万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750020
• 关键词: 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 examples where randomized algorithms have been successfully de-randomized to become parallel algorithms. Furthermore, when such a de-randomization is possible, we do not know how much parallelism is required. My interest in conceptually simple algorithms has led me to various problems in the field of algorithmic game theory/mechanism design (AGT). One fundamental problem is when can good approximations be turned into good mechanisms given that self-interested agents are providing the inputs.For example, in auctions the underlying allocation algorithms needs to be conceptually simple for the auction mechanism to be adopted in practice. Perhaps the simplest type of auction mechanism is a posted price mechanism where agents (in some order) are offered prices for various bundles of goods and then must make a ``take it or leave it'' choice as to what to purchase. How such a mechanism price items or when there is no mechanism what are the eqquilibrium prices and what are the dynamics that can lead to equilibria. In the related field of social choice theory, I am also considering algorithmic questions concerning the use of various voting rules. And in other somewhat related fields, I am also interested in how influence spreads in a social network and how one achieves stable matchings given only partial (e.g. probabilistic) information as to preferences.

这项建议涉及若干不同的研究领域。然而，我最近的研究兴趣往往是由问题的动机，什么可以和不能计算的“概念上简单的算法”。在这方面，我的主要兴趣关注概念上简单的组合优化问题的近似算法。更具体地说，我正在研究在线和贪婪算法，原始对偶算法，动态规划算法，局部算法和局部搜索的各种形式和扩展。最近，我一直在关注一些领域，在这些领域中，相当天真的随机化往往比更“有原则”和复杂的确定性算法更好。 作为例子，我们可以问，什么是最简单的确定性一遍算法，可以匹配或超过3/4近似比实现的各种算法的最大卫星问题和相同的问题，以超过1-1/e近似在线二分匹配。特别是，我正在研究并行和多通道在线和贪婪算法。最近已经表明，这样的算法有时可以从随机算法中推导出来。然而，到目前为止，只有一对夫妇的例子，随机算法已被成功地去随机化，成为并行算法。此外，当这种去随机化是可能的时，我们不知道需要多少并行性。 我对概念上简单的算法的兴趣使我在算法博弈论/机制设计（AGT）领域遇到了各种问题。一个基本的问题是，在给定自利主体提供输入的情况下，什么时候好的近似可以转化为好的机制。例如，在拍卖中，底层的分配算法需要在概念上简单，以便在实践中采用拍卖机制。也许最简单的拍卖机制是公布价格机制，在这种机制中，代理人（按某种顺序）被提供各种捆绑货物的价格，然后必须就购买什么作出“接受或放弃”的选择。这样的机制如何定价项目，或者当没有机制时，什么是均衡价格，什么是可以导致均衡的动态。在社会选择理论的相关领域，我也在考虑有关使用各种投票规则的算法问题。在其他一些相关的领域，我也对影响力如何在社交网络中传播以及如何在只给出部分（例如概率）偏好信息的情况下实现稳定匹配感兴趣。