Approximation Algorithms and Hardness of Approximation for Optimization Problems

我目前和计划中的研究重点是设计和分析有效的近似算法，以解决网络设计、调度或计算经济等应用中自然出现的优化问题。大多数现实世界的优化问题，比如网络设计中的问题，都是np困难的。因此，在“P不等于NP”的假设下，我们无法最优有效地（即在合理的时间内）解决这些问题。鉴于此，通常可以有效地计算出接近最优的解决方案。因此研究主要集中在近似算法的研究上；这些算法运行速度快，产生的解在最优解的保证因子范围内。

My current and planned research focuses on design and analysis of efficient approximation algorithms for optimization problems that naturally arise in applications such as network design, scheduling, or computational economy. Most of the real world optimization problems, such as the ones in design of networks, are NP-hard. Therefore, under the assumption of "P not equal to NP", we cannot solve these problems optimally and efficiently (i.e. in a reasonable amount of time). Given this, it is typically acceptable to compute a near optimal solution efficiently. So research has focused on the study of approximation algorithms; these are algorithms that run fast and produce a solution that is within a guaranteed factor of the optimal one.