Approximation Algorithms and Hardness of Approximation for Optimization Problems

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

• 批准号: RGPIN-2018-04677
• 负责人: Salavatipour, Mohammad
• 金额: $ 6.99万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750517
• 关键词: 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.

理论计算机科学是一个多元化的领域。理论计算机科学的研究可以跨越不同的子领域，但这里讨论的那些领域是受到现实世界应用程序的启发。典型地，这些是从某些应用程序发起的优化问题，并且需要首先以数学形式表述问题，其中我们希望优化某些目标函数(例如，成本、时间、vs.服务质量、利润)。然后，下一步是为该问题开发一个算法，并对其性能和正确性进行严格的分析。由于这些问题大多是NP难的，除非P\NOT=NP，否则我们不能有效地确定它们的最优解。因此，以逼近算法的研究为核心的研究应运而生。这些算法运行速度很快(通常意味着多项式时间)，并且产生的解保证在最优解的某个已证明的因素内。也许研究这些类型的算法的一个重要动机因素是，所开发的技术和算法工具往往在其他情况下非常有用，即使近似算法本身可能不是很实用。还值得指出的是，尽管在分析中获得的最差性能比率可能看起来相当糟糕，但在许多情况下，实际性能要好得多。研究逼近的难易程度，即证明问题的可逼近下界也很重要。这项研究往往会使我们对NP-Hard优化问题的谱有更深刻的理解，并可以用来开发新的更好的近似算法。我一直在研究的一些主要课题包括：近似算法的设计和分析，逼近的难度，算法设计和下界证明中的概率方法和随机化方法，组合学和算法图论。更具体地说，在接下来的几年里，我的计划是专注于研究一些集群问题，定向问题，以及调度和资源分配问题。希望在一般情况下和/或在应用中更频繁地出现的一些特殊情况下，针对这些问题设计更好的近似算法。