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 thequality of solution for the computation time. Approximation algorithms do precisely that. Approximationalgorithms not only provide an approximate solution in polynomial time, they also provide a certificate ofoptimality for the solution. One can always refine and tune an approximation algorithm to specific class ofinstances 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. Wewill design approximation algorithms for problems arising in the bioinformatics, facility location, schedul-ing, and machine learning domains. Our approach for designing approximation algorithms has theoreticalunderpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programmingbased 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 integralsolution using some scheme. Care is taken to ensure that the process of converting the fractional solution toan 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 usingthe primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sizedformulation without having to resort to a separation oracle. Approaches based on the primal-dual schemahave 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 betterthan the integrality gap of the relaxation. Therefore integer programs with small integrality gap are criticalto the success of such approximation algorithms. The immediate program is i) to develop relaxations withbounded 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 strategiesfor converting the fractional solutions to the relaxations to integral solution. There has been considerableresearch 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 approximationalgorithms 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 aspart 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 qualityjournals and conferences. The program will produce highly skilled manpower; skilled in the use of discreteoptimization theory and tools.