Approximation algorithms for hard optimization problems in multi-omics research and operations research

多组学研究和运筹学中硬优化问题的近似算法

• 批准号: RGPIN-2019-05258
• 负责人: Lin, Guohui
• 金额: $ 2.99万
• 依托单位: 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=715436
• 关键词: Approximation; algorithms; hard; optimization; problems

The proposed research program focuses on designing efficient algorithms with provable performance for computational optimization problems inspired by real world applications, in particular from multi-omics research and operations research. When facing a challenging real world application, the typical process is first to formulate the problem mathematically, to pursue the optimization of a specified objective function. The optimization problem is then studied to understand its level of difficulty and to design algorithms supported by a rigorous analysis of its efficiency, performance and correctness. But most of our target problems arising from challenging applications cannot be solved optimally in polynomial time, unless P = NP. We follow the line of main stream research to study the in-/approximability of the problems and to design approximation algorithms for the problems. Additionally, we will study the fixed parameter tractability of the problems and seek to pioneer the fixed parameter approximability. Approximation algorithms run in polynomial time and produce solutions that are guaranteed to be within a certain factor of the optimal solution. The study of the design and analysis of approximation algorithms has multi-faceted impact: 1) due to the intractability of the target optimization problem, an approximation algorithm at least gives a way to find a near-optimal solution with provable guarantee; 2) although the worst-case performance guarantee may appear disappointing, an approximation algorithm can frequently perform really well on real world instances; and 3) most importantly, the developed algorithmic tools and design-and-analysis techniques can be generally useful, even if the approximation algorithm by itself may not be very practical. While approximation algorithms are positive results for approaching an NP-hard problem, it is also important to study the limit of such approximation, known as the hardness of approximation or inapproximability. By proving lower bounds on approximability of the problems, we achieve deeper insights on the spectrum of the NP-hard optimization problems. Such insights can in turn be used to develop new and better approximation algorithms. The tractability and the approximability of the problem could change along with the (often multiple) parameters and/or output. Fixed parameter tractability has been extensively investigated, but results on how the approximability of the problems changes along with the parameters in the input or output are limited. The study on approximation algorithms with both running time and performance ratio depending on a parameter k has the same multi-faceted aspects as stated in the above, and additionally provides insights on the parameter k and subsequently another deeper understanding of the internal spectrum of the target optimization problem.

拟议的研究计划侧重于设计具有可证明性能的高效算法，以解决受现实世界应用启发的计算优化问题，特别是多组学研究和运筹学。当面对具有挑战性的现实世界应用时，典型的过程是首先以数学方式表述问题，以追求指定目标函数的优化。然后研究优化问题以了解其难度级别并设计算法，并对其效率、性能和正确性进行严格分析。但是，我们的大多数由具有挑战性的应用程序引起的目标问题无法在多项式时间内得到最佳解决，除非 P = NP。我们遵循主流研究的路线来研究问题的内/逼近性并设计问题的逼近算法。此外，我们将研究问题的固定参数可处理性，并寻求开创固定参数逼近性。 近似算法在多项式时间内运行，并生成保证在最佳解决方案的某个因素内的解决方案。对近似算法的设计和分析的研究具有多方面的影响：1）由于目标优化问题的棘手性，近似算法至少给出了一种找到具有可证明保证的近最优解的方法； 2）尽管最坏情况下的性能保证可能会令人失望，但近似算法通常可以在现实世界的实例上表现得非常好； 3）最重要的是，所开发的算法工具和设计与分析技术通常是有用的，即使近似算法本身可能不太实用。 虽然近似算法对于解决 NP 难问题有积极的结果，但研究这种近似的极限也很重要，即近似的硬度或不可近似性。通过证明问题近似性的下界，我们对 NP 难优化问题有了更深入的了解。这些见解反过来可用于开发新的、更好的近似算法。 问题的易处理性和近似性可能会随着（通常是多个）参数和/或输出而变化。固定参数的可处理性已经被广泛研究，但是关于问题的近似性如何随着输入或输出中的参数而变化的结果是有限的。对运行时间和性能比取决于参数 k 的近似算法的研究具有与上述相同的多方面，并且还提供了对参数 k 的见解以及随后对目标内部频谱的另一个更深入的理解优化问题。