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.