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。我的研究兴趣集中在近似算法的设计上。我对两类问题的近似算法的研究特别感兴趣：网络和包装问题。网络是优化中最基本的建模工具之一，应用于许多领域。布局问题在运输、超大规模集成电路设计、调度和任何其他需要在有界空间中安排物体的应用领域中具有非常重要的意义。在这项研究计划中，我们将追求以下短期目标：**-研究在设施定位和聚类问题的近似算法设计中结合使用局部搜索和其他优化技术。针对输入受限的装箱与排程问题，设计固定参数且易于处理的近似演算法。 **-为非常大的网络（如社交网络）中的聚类问题设计高效的近似算法。 **-设计有效的实验技术来分析和改进近似算法的性能。