Approximation algorithms for optimization problems

优化问题的近似算法

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

Combinatorial optimization deals with finding optimum solutions for problems of a discrete and finite nature. Such problems arise in areas as diverse as Computer Science, Mathematics, Finances, Biology, Medicine, and Operations Research, among others. Many of these problems are too complex to solve without the use of computers and, therefore, efficient algorithms for solving them are needed. ******There is strong theoretical evidence suggesting that for many combinatorial optimization problems no polynomial time algorithm can compute exact solutions for them. Such problems get the technical name of NP-hard. One fundamental tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values can be proven to be no more than some factor c away from the optimum.******My research interests center on the design of approximation algorithms. I am particularly interested in the study of approximation algorithms for two kinds of problems: Network and packing problems. Networks are one of the most fundamental modelling tools in optimization, with application to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other application domains requiring the arrangement of objects in bounded spaces.******Within this research proposal we will pursue the following short term goals:******- Investigate the combined use of local search and other optimization techniques in the design of approximation algorithms for facility location and clustering problems.******- Design fixed parameter tractable approximation algorithms for packing and scheduling problems with restricted inputs. ******- Design efficient approximation algorithms for clustering problems in very large networks, like social networks. ******- Design effective experimental techniques for analyzing and improving the performance of approximation algorithms.

组合优化涉及寻找离散和有限性质问题的最佳解决方案。此类问题出现在计算机科学、数学、金融、生物学、医学和运筹学等各个领域。其中许多问题过于复杂，如果不使用计算机就无法解决，因此需要有效的算法来解决这些问题。 ******有强有力的理论证据表明，对于许多组合优化问题，没有多项式时间算法可以计算出它们的精确解。此类问题的技术名称为 NP 难问题。处理这些问题的一种基本工具是近似算法。这些是有效的算法，可以产生解决方案，其值可以证明与最佳值的距离不超过某个因子 c。 *****我的研究兴趣集中在近似算法的设计上。我对研究两类问题的近似算法特别感兴趣：网络问题和打包问题。网络是优化中最基本的建模工具之一，应用于许多领域。包装问题在运输、VLSI 设计、调度以及任何其他需要在有限空间中排列物体的应用领域中非常重要。******在本研究提案中，我们将追求以下短期目标：*** ***- 研究在设施定位和聚类问题的近似算法设计中结合使用局部搜索和其他优化技术。******- 为输入受限的打包和调度问题设计固定参数易处理的近似算法。 ******- 为大型网络（例如社交网络）中的聚类问题设计高效的近似算法。 ******- 设计有效的实验技术来分析和改进近似算法的性能。