Approximation Algorithms for NP-hard Optimization Problems

一般认为，对于NP-hard优化问题，不存在寻找最优解的有效算法。处理无法有效地找到精确解的一种自然方法是用解的质量来换取计算时间。近似算法就是这样做的。近似算法不仅在多项式时间内提供近似解，而且还提供了解的最优性证明。人们总是可以根据实践中出现的特定类型的实例来改进和调整近似算法，从而提高性能比率。**本研究的主要目标是进一步推动近似算法设计的理论和实践。我们将为生物信息学、设施定位、调度和机器学习领域出现的问题设计近似算法。我们设计近似算法的方法有组合算法、线性和半确定规划的理论基础。基于线性规划*的方法在最近获得了巨大的成功。基本框架需要将优化问题描述为整数线性规划或整数变量上的非线性规划。**构造了一个合适的线性规划松弛或半确定规划松弛。用高效的算法求解了松弛问题。用某种格式将得到的分数解转换为积分解。要注意确保将分数解转换为积分解的过程不会过多地增加解的成本。另一种方法是使用原始-对偶模式同时迭代构造一个积分原始解和候选对偶解（可能是分数）。原始对偶模式的优点是可以使用指数大小的*公式，而不必求助于分离oracle。基于原始对偶模式*的方法对于某些类型的优化问题已经非常成功。整数规划公式的完整性缺口是最优分数的代价与最优积分解的代价之间的缺口。**基于线性或半确定规划的近似算法的性能比不优于*松弛的完整性间隙。因此，具有小完整性间隙的整数程序对于这种近似算法的成功是至关重要的。直接的计划是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.