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.