Approximation Algorithms and Hardness of Approximation for Optimization Problems

我目前和计划中的研究重点是设计和分析有效的近似算法的优化问题，自然出现在应用程序，如网络设计，调度，或计算经济。大多数真实的优化问题，如网络设计问题，都是NP难问题。因此，在“P不等于NP”的假设下，我们无法最佳和有效地解决这些问题（即在合理的时间内）。考虑到这一点，通常可以有效地计算接近最优的解决方案。因此，研究集中在近似算法的研究上;这些算法运行速度快，并产生一个解决方案，该解决方案是在最佳解决方案的保证因素之内。这些算法中的许多都被应用于解决这些难题。也许研究近似算法的一个重要激励因素是，通常开发的技术和算法工具在其他情况下可能非常有用，即使近似算法本身可能不是实践中的最佳算法。在硬优化问题中，与图和网络设计相关的问题特别重要，在过去几十年中引起了很多关注，最近由于更复杂的约束，网络设计越来越复杂。这些问题包括，更一般的最小费用网络流，网络连接与多个约束，和相关的切割问题，以及一些问题，从计算经济。研究逼近的困难性也是很重要的，它是为了证明问题的可逼近性的下界。这有助于将所提出的近似算法的质量的角度来看，反过来可以用来设计更好的算法。在过去的二十年里，这条研究路线一直非常活跃，特别是自从概率可检验证明系统和PCP定理的发展以来。我已经成功地应用组合和概率技术的设计和分析的近似算法，以及证明这些问题的下限，并将继续在这方面的工作。

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. Many of these algorithms are used in applications to attack these hard problems. Perhaps one of the important motivating factors of study of approximation algorithms is that often the techniques and algorithmic tools developed can be quite useful in other contexts, even if the approximation algorithm by itself may not be the best algorithm in practice. Among the hard optimization problems, those related to graphs and network design are particularly important and have drawn a lot of attention over the last few decades, and more so recently with the growing complications in the design of networks due to more sophisticated constraints. These problems include, more general minimum cost network flows, network connectivity with several constraints, and related cut problems, as well as some problems that arise from computational economy. It is also important to study hardness of approximation which is to prove lower bounds on approximability of the problems. This helps to put the quality of the proposed approximation algorithms in perspective and in turn could be used to design better algorithms. This line of research has been very active in the last two decades, specially since the development of Probabilistic Checkable Proof systems and the PCP theorem. I have successfully applied combinatorial and probabilistic techniques in the design and analysis of approximation algorithms as well as proving lower bounds for these problems and will continue to work in this area.