Approximation Algorithms and Hardness of Approximation for Optimization Problems

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

Theoretical Computer Science is a diverse area. Research in theoretical computer science can span various sub-areas, but the ones considered here are inspired by real world applications. Typically these are optimization problems initiated from some application and there is a need to first formulate the problem mathematically in which we wish to optimize some objective function (e.g. cost, time, v.s. quality of service, profit). Then the next step is to develop an algorithm for the problem backed by a rigorous analysis of its performance and correctness. Since most of these problems are NP-hard, unless P \not= NP, we cannot determine their optimal solution efficiently. Therefore, a line of research has emerged with focus on the study of approximation algorithms. These are algorithms that run fast (typically meant polynomial time) and produce solutions that are guaranteed to be within some proven factor of the optimal solution. Perhaps one of the important motivating factors of study of these types of 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 very practical. It is also worth pointing out that, although the worst performance ratio obtained in the analysis might seem quite bad, in many situation the actual performance in reality is much better. It is also important to study hardness of approximation, i.e. prove lower bounds on approximability of problems. This study often yields a deeper understanding of the spectrum of the NP-hard optimization problems we have and can be used to develop new and better approximation algorithms.******Some of the major topics that I have been doing research on can be listed as: design and analysis of approximation algorithms, hardness of approximation, the probabilistic and randomized methods in design of algorithms and proving lower bounds, combinatorics, and algorithmic graph theory. More specifically, over the next few years my plan is to focus on study of some clustering problems, orienteering problems, and scheduling and resource allocation problems. The hope is to design better approximation algorithms for these problems in general settings and/or in some special cases that appear in applications more often.