Approximation Algorithms and Hardness of Approximation for Optimization Problems

点击翻译按钮获取中文摘要

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.