Approximation Algorithms for NP-hard Optimization Problems

NP 难优化问题的近似算法

• 批准号: RGPIN-2014-06302
• 负责人: Gaur, Daya
• 金额: $ 1.46万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=567720
• 关键词: Approximation; Algorithms; NP; hard; Optimization

It is generally believed that efficient algorithms do not exist for finding an optimal solution to NP-hard opti- mization problems. A natural way to deal with the inability to find exact solutions efficiently is to trade the quality of solution for the computation time. Approximation algorithms do precisely that. Approximation algorithms not only provide an approximate solution in polynomial time, they also provide a certificate of optimality for the solution. One can always refine and tune an approximation algorithm to specific class of instances arising in practice, thereby improving the performance ratio. Primary goal of this research is to further the theory and praxis of the design of approximation algorithms. We will design approximation algorithms for problems arising in the bioinformatics, facility location, schedul- ing, and machine learning domains. Our approach for designing approximation algorithms has theoretical underpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programming based approaches have enjoyed a great deal of success in the recent past. The basic framework entails de- scribing the optimization problem as an integer linear program or a non-linear program over integer variables. A suitable linear programming relaxation or a semi-definite programming relaxation is constructed. The re- laxation is solved using efficient algorithms. A fractional solution thus obtained is converted to an integral solution using some scheme. Care is taken to ensure that the process of converting the fractional solution to an integral solution does not increase the cost of the solution too much. Another approach is to simultane- ously construct an integral primal solution and candidate dual solution (possibly fractional) iteratively using the primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sized formulation without having to resort to a separation oracle. Approaches based on the primal-dual schema have been very successful for certain types of optimization problems. Integrality gap of an integer program- ming formulation is the gap in the cost of the optimal fractional and the cost of the optimal integral solution. Approximation algorithms based on linear or semi-definite programming have performance ratio no better than the integrality gap of the relaxation. Therefore integer programs with small integrality gap are critical to the success of such approximation algorithms. The immediate program is i) to develop relaxations with bounded integrality gap for the optimization problems of interest or show none exists, ii) to develop combi- natorial algorithms for solving the relaxations where possible, and iii) to develop provably good strategies for converting the fractional solutions to the relaxations to integral solution. There has been considerable research activity on the hardness of approximations in the last few years and several deep results on the hard- ness of approximations have been obtained. The focus of this research is on the design of approximation algorithms and we will draw on the results on hardness of approximations to guide the program. On the theoretical front we will push the frontier in approximation algorithms design. Research conducted as part of this project will have prospect for commercialization and will be of immediate interest to the industry. Knowledge generated will be protected using patents (where applicable) and disseminated in high quality journals and conferences. The program will produce highly skilled manpower; skilled in the use of discrete optimization theory and tools.

通常认为，为找到NP-HARD掌握问题的最佳解决方案而没有有效的算法。处理无法有效找到确切解决方案的自然方法是在计算时间内交易解决方案的质量。近似算法正是这样做的。近似算法不仅在多项式时间内提供了近似解决方案，还为解决方案提供了最佳证书。人们总是可以对实践中产生的特定类别的实例进行完善并调整近似算法，从而提高性能比。这项研究的主要目标是进一步概述算法设计的理论和实践。我们将设计在生物信息学，设施位置，调度和机器学习域中出现的问题的近似算法。我们设计近似算法的方法具有理论上的基础，该基础是组合算法，线性和半定义编程。在最近的过去，基于线性编程的方法取得了很大的成功。基本框架需要将优化问题描述为整数线性程序或整数变量上的非线性程序。构建了合适的线性编程松弛或半明确编程放松。使用有效的算法解决重新释放。这样获得的分数溶液使用某些方案将其转换为积分解决方案。要确保将分数溶液转换为积分解决方案的过程不会过多地增加解决方案的成本。另一种方法是使用原始偶型架构同时构建一个积分原始解决方案和候选双解（可能是分数）。原始偶型架构的优点是，一个人可以使用指数尺寸的公式，而无需诉诸于分离的Oracle。对于某些类型的优化问题，基于原始偶型架构的方法非常成功。整数程序公式的完整性差距是最佳分数成本和最佳积分解决方案的成本的差距。基于线性或半明确编程的近似算法的性能比不比放松的完整性差距更好。因此，具有较小完整性差距的整数程序对于此类近似算法的成功至关重要。 i）i）i）在有界的整体差距中发展放松，以使感兴趣的优化问题或表明不存在，ii）开发出解决放松的组合算法，并在可能的情况下解决iii），以开发可证明的良好策略，以将分数解决方案转化为放松方案，从而将分数解决方案转化为积分解决方案。在过去几年中，有关近似值的硬度的研究活动已有很多，并且已经获得了近似值的深刻结果。这项研究的重点是近似算法的设计，我们将利用近似值的结果来指导该程序。在理论方面，我们将以近似算法设计将边界推向前沿。作为该项目的一部分进行的研究将具有商业化的前景，并将引起行业的直接利益。产生的知识将受到专利（适用）的保护，并在高质量的期刊和会议上进行传播。该计划将产生高技能的人力；熟练使用离散优化理论和工具。