Approximation Algorithms for NP-hard Optimization Problems

NP 难优化问题的近似算法

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