Approximation Algorithms for Combinatorial Optimization Problems

组合优化问题的近似算法

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

Many optimization problems in manufacturing, transportation, communications, finances, and many other fields require solutions that optimize the use of available resources. An important class of these problems are combinatorial optimization problems. Many of these problems are too complex to solve without the use of computers and, hence, efficient computer algorithms for solving them are needed. However, there is strong theoretical evidence suggesting that even modern fast computers are not powerful enough to efficiently solve many of these optimization problems; these problems get the technical name of NP-hard. Despite the seeming impossibility for solving NP-hard problems efficiently (or,technically, in polynomial time), we still need to deal with them since they arise in industrial and commercial applications. One important tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values are within some factor c from the optimum. Knowing how close to optimal are the solutions produced by approximation algorithms helps us determine how well we can solve complex problems of practical relevance. This research focuses on the design of approximation algorithms for three kinds of problems: network, scheduling and packing problems. Networks are one of the most fundamental modelling tools in optimization and scheduling and packing problems are of great importance in domains requiring the effective management of limited resources. Goals: 1. To design efficient approximation algorithms that exploit the special structure of restricted instances of scheduling, packing, and network optimization problems that arise in practical applications. The inherent nature of practical applications many times restricts the set of inputs that my appear in instances of optimization problems arising from them. I plan to work on exploiting the structure of these restricted instances to discover good design techniques for them. 2. To formulate new techniques for the design of approximation algorithms for scheduling, packing, and network problems that yield approximation algorithms with practical running times. I will work on extending and combining existing design techniques for approximation algorithms so they are applicable to a larger set of problems. 3. To study the trade-off between the quality of solutions produced by approximation algorithms and their running times. In practical applications it is necessary to limit the amount of time that an algorithm can run. I plan to work on understanding what is the best solution that one can hope to obtain for a particular problem within a given amount of time. I expect my research to lead to approximation algorithms that are better suited than existing ones for practical applications of network, scheduling and packing problems, both with respect to approximation ratio and running time. This research is of theoretical and practical importance.

制造、运输、通信、金融和许多其他领域的许多优化问题需要能够优化可用资源使用的解决方案。这些问题中的一类重要问题是组合优化问题。其中许多问题过于复杂，如果不使用计算机就无法解决，因此需要有效的计算机算法来解决这些问题。然而，有强有力的理论证据表明，即使是现代的快速计算机也不足以有效地解决许多此类优化问题；这些问题得到了 NP 难题的技术名称。尽管似乎不可能有效地（或者从技术上讲，在多项式时间内）解决 NP 难题，但我们仍然需要处理它们，因为它们出现在工业和商业应用中。处理这些问题的一个重要工具是近似算法。这些是有效的算法，产生的解决方案的值在最佳值的某个因子 c 内。了解近似算法产生的解决方案与最优解的接近程度有助于我们确定解决实际相关的复杂问题的能力。本研究重点关注三类问题的近似算法设计：网络、调度和打包问题。网络是优化和调度中最基本的建模工具之一，而打包问题在需要有效管理有限资源的领域中非常重要。目标： 1. 设计有效的近似算法，利用实际应用中出现的调度、打包和网络优化问题的受限实例的特殊结构。实际应用的固有性质很多时候限制了在由此产生的优化问题实例中出现的输入集。我计划致力于利用这些受限实例的结构来发现适合它们的良好设计技术。 2. 制定用于调度、打包和网络问题的近似算法设计的新技术，从而产生具有实际运行时间的近似算法。我将致力于扩展和组合近似算法的现有设计技术，以便它们适用于更大的问题集。 3. 研究近似算法产生的解的质量与其运行时间之间的权衡。在实际应用中，有必要限制算法可以运行的时间。我计划努力了解人们希望在给定时间内针对特定问题获得的最佳解决方案是什么。 我希望我的研究能够产生比现有算法更适合网络、调度和打包问题实际应用的近似算法，无论是在近似率还是运行时间方面。本研究具有重要的理论和实践意义。