Approximation Algorithms for NP-hard Optimization Problems

NP 难优化问题的近似算法

• 批准号: RGPIN-2014-06302
• 负责人: Gaur, Daya
• 金额: $ 1.46万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=651598
• 关键词: 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-难优化问题的最优解。解决无法有效找到精确解的问题的一个自然方法是用解的质量来换取计算时间。近似算法正是这样做的。近似算法不仅在多项式时间内提供近似解，还为解提供最优性证明。人们总是可以根据实际中出现的特定类别的 * 实例来改进和调整近似算法，从而提高性能比。本研究的主要目的是进一步深化近似算法设计的理论和实践。我们将为生物信息学、设施定位、机器学习和机器学习领域中出现的问题设计近似算法。我们设计近似算法的方法在组合算法、线性和半定规划中有理论基础。基于线性规划 * 的方法在最近的过去取得了很大的成功。基本框架需要将优化问题描述为整数变量上的整数线性规划或非线性规划。构造了一个合适的线性规划松弛或半定规划松弛。使用有效的算法解决了重新定义。这样得到的分数阶解用某种方法转化为积分阶解。注意确保将分数解转换为积分解的过程不会过多地增加解的成本。另一种方法是使用原始-对偶模式迭代地同时构造积分原始解和候选对偶解（可能是分数）。原始-对偶模式的优点是可以使用指数大小的 * 公式，而不必求助于分离预言机。基于原始-对偶模式 * 的方法对于某些类型的优化问题非常成功。整数规划的积分间隙是最优分数解的代价和最优积分解的代价之间的差距。基于线性或半定规划的近似算法的性能比并不比松弛的完整性间隙好。因此，具有小整数间隙的整数规划是此类近似算法成功的关键。直接的程序是i）为感兴趣的优化问题开发具有有界积分间隙的松弛或显示不存在，ii）在可能的情况下开发用于求解松弛的组合算法，以及iii）开发用于将分数解转换为松弛解的可证明的好策略。在过去的几年里，关于逼近的难性有相当多的研究活动，并且已经得到了一些关于逼近的难性的深入结果。本研究的重点是近似算法的设计，我们将利用近似的硬度结果来指导程序。在理论方面，我们将推动近似算法设计的前沿。作为本项目的一部分进行的研究将具有商业化的前景，并将对工业产生直接影响。产生的知识将使用专利（如适用）进行保护，并在高质量 * 期刊和会议上传播。该计划将产生高度熟练的人力;熟练使用离散 * 优化理论和工具。