组合优化近似算法的设计与分析

实际应用中碰到的许多优化问题是NP难解的，在组合优化学科中的绝大多数著名问题属于所谓的NP完备问题，除非P=NP,人们不可能对它们找到多项式时间的算法。因此，人们设法从各种渠道来寻找处理它们的办法。其中一个有效而合理的办法是采用近似算法来求解。此时要求设计出多项式时间的算法，并要求估计出：在这种算法之下，所得到的解对应的目标函数的值与最优解对应的目标函数的值之间的差距(近似比)。选址问题是运筹学里的核心问题之一, 它来自于工厂，仓库，学校，医院等位置的确定问题，当今的应用包括网络上代理服务器的安置问题。多层选址问题和多层选址对策在供应链管理中有非常重要的应用。排序，图划分，覆盖和装箱等问题组合优化里面的著名问题。研究半定规划，线性规划和凸二次规划在设计近似算法中的应用是国际上的研究热点之一。