Approximation Algorithms for NP-hard Optimization Problems

一般认为，对于NP-Hard最优解的求解，并不存在有效的算法。 移动化问题。处理无法有效地找到准确解决方案的自然方法是在 计算时间的解的质量。近似算法正是做到了这一点。近似值 算法不仅在多项式时间内提供了近似解，它们还提供了 解的最优性。人们总是可以改进和调整近似算法，以适应特定类别的 实例，从而提高了性能比。 本研究的主要目的是进一步深化逼近算法设计的理论和实践。我们 将为生物信息学、设施选址、调度中出现的问题设计近似算法- ING和机器学习领域。我们设计近似算法的方法有理论上的 组合算法、线性规划和半定规划的基础。线性规划 在最近的过去，基于方法的方法获得了巨大的成功。基本框架需要去-- 将优化问题描述为整数线性规划或整数变量上的非线性规划。 构造了一个合适的线性规划松弛或半定规划松弛。再一次- 松弛是用有效的算法解决的。这样得到的分数解被转换成积分 使用某种方案的解决方案。注意确保将分数解转换为 完整的解决方案不会使解决方案的成本增加太多。另一种方法是模拟- 使用以下方法迭代构造积分原解和候选对偶解(可能是分数次) 原始-对偶模式。原始-对偶模式的优点是可以处理指数大小的 无需求助于分离神谕的配方。基于原始-对偶模式的方法 在某些类型的优化问题上已经非常成功。整数规划完整性差-- 明式是最优分数解的代价与最优积分解的代价之差。 基于线性或半定规划的近似算法的性能比也好不到哪里去 而不是松弛的完整性间隙。因此，具有小完整性间隔的整数规划是至关重要的 为这种近似算法的成功干杯。直接的计划是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.