Approximation Algorithms for NP-hard Optimization Problems

一般认为，对于NP-Hard最优化问题，并不存在有效的算法来寻找最优解。处理无法有效地找到精确解的一个自然方法是用解的质量来换取计算时间。近似算法正是做到了这一点。近似*算法不仅在多项式时间内提供近似解，而且还提供解的*最优性证明。人们总是可以针对实际中出现的特定类型的实例来改进和调整近似算法，从而提高性能比。**本研究的主要目标是深化近似算法设计的理论和实践。我们将为生物信息学、设施选址、调度和机器学习领域中出现的问题设计近似算法。我们设计近似算法的方法有组合算法、线性规划和半定规划的理论基础。最近，基于线性规划*的方法获得了巨大的成功。基本框架需要将优化问题描述为整数线性规划或关于整数变量的非线性规划。**构造适当的线性规划松弛或半定规划松弛。用高效的算法解决了松弛问题。这样得到的分数阶解使用某种格式转换为积分*解。注意确保将分数解转换为*整数解的过程不会使解决方案的成本增加太多。另一种方法是使用原始-对偶模式迭代地同时构造积分原始解和候选对偶解(可能是分数次)。原始-对偶模式的优点是可以处理指数大小的*公式，而不必求助于分离预言。对于某些类型的优化问题，基于原始-对偶模式的方法已经非常成功。整数规划的完整性缺口是指最优分数解的成本和最优整数解的成本之间的缺口。基于线性或半定规划的**近似算法的性能比并不比松弛的完整性缺口好。因此，具有较小整数间隔的整数规划是此类近似算法成功的关键。直接的计划是i)为感兴趣的优化问题开发具有*有界积分间隙的松弛，或者证明不存在松弛，ii)在可能的情况下开发解决松弛的组合自然算法，以及iii)开发可证明是好的策略*将分数解转换为积分解。在过去的几年里，关于逼近的难易程度已经有了相当多的研究活动，并且已经得到了关于逼近难易的几个深刻的结果。本研究的重点是逼近算法的设计，我们将利用逼近硬度的结果来指导程序。**在理论方面，我们将推动逼近算法设计的前沿。作为这个项目的一部分进行的研究将有商业化的前景，并将立即引起业界的兴趣。*产生的知识将使用专利(在适用的情况下)加以保护，并在高质量的*期刊和会议上传播。该计划将培养出高技能的人力；熟练使用离散*优化理论和工具。

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.