Approximation Algorithms and Hardness of Approximation for Optimization Problems

优化问题的逼近算法和逼近难度

• 批准号: RGPIN-2018-04677
• 负责人: Salavatipour, Mohammad
• 金额: $ 3.5万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=713176
• 关键词: Approximation; Algorithms; Hardness; Optimization; Problems

Theoretical Computer Science is a diverse area. Research in theoretical computer science can span various sub-areas, but the ones considered here are inspired by real world applications. Typically these are optimization problems initiated from some application and there is a need to first formulate the problem mathematically in which we wish to optimize some objective function (e.g. cost, time, v.s. quality of service, profit). Then the next step is to develop an algorithm for the problem backed by a rigorous analysis of its performance and correctness. Since most of these problems are NP-hard, unless P \not= NP, we cannot determine their optimal solution efficiently. Therefore, a line of research has emerged with focus on the study of approximation algorithms. These are algorithms that run fast (typically meant polynomial time) and produce solutions that are guaranteed to be within some proven factor of the optimal solution. Perhaps one of the important motivating factors of study of these types of algorithms is that often the techniques and algorithmic tools developed can be quite useful in other contexts, even if the approximation algorithm by itself may not be very practical. It is also worth pointing out that, although the worst performance ratio obtained in the analysis might seem quite bad, in many situation the actual performance in reality is much better. It is also important to study hardness of approximation, i.e. prove lower bounds on approximability of problems. This study often yields a deeper understanding of the spectrum of the NP-hard optimization problems we have and can be used to develop new and better approximation algorithms. Some of the major topics that I have been doing research on can be listed as: design and analysis of approximation algorithms, hardness of approximation, the probabilistic and randomized methods in design of algorithms and proving lower bounds, combinatorics, and algorithmic graph theory. More specifically, over the next few years my plan is to focus on study of some clustering problems, orienteering problems, and scheduling and resource allocation problems. The hope is to design better approximation algorithms for these problems in general settings and/or in some special cases that appear in applications more often.

理论计算机科学是一个多样化的领域。理论计算机科学的研究可以跨越各个子领域，但这里考虑的是受真实的世界应用的启发。通常，这些是从一些应用程序开始的优化问题，并且需要首先在数学上将问题公式化，其中我们希望优化一些目标函数（例如，成本，时间，与...服务质量、利润）。然后，下一步是开发一个算法的问题，通过严格的分析其性能和正确性的支持。由于这些问题中的大多数是NP难的，除非P \not= NP，否则我们无法有效地确定它们的最优解。因此，出现了一系列的研究，重点是近似算法的研究。这些算法运行速度快（通常意味着多项式时间），并产生保证在最优解的某个已验证因子内的解决方案。也许这些类型的算法的研究的一个重要的激励因素是，通常开发的技术和算法工具可以在其他情况下是非常有用的，即使近似算法本身可能不是很实用。还值得指出的是，虽然分析中获得的最差性能比可能看起来很差，但在许多情况下，实际性能要好得多。研究逼近的难度也很重要，即证明问题的可逼近性的下界。这项研究往往会产生一个更深入的了解频谱的NP-难优化问题，我们可以用来开发新的和更好的近似算法。 我一直在研究的一些主要课题可以列为：近似算法的设计和分析，近似的硬度，算法设计和证明下界的概率和随机方法，组合学和算法图论。更具体地说，在接下来的几年里，我的计划是集中研究一些集群问题，定向越野问题，调度和资源分配问题。希望能为这些问题在一般情况下和/或在一些特殊情况下，更经常出现在应用程序中设计更好的近似算法。