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.