Linear programming based approximation algorithms for optimization problems

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

Approximation algorithms are an elegant formal framework for dealing with intrinsically hard optimization problems. An approximation algorithm for an optimization problem produces a feasible solution in polynomial time that is within a constant multiplicative factor of the optimal solution for every instance of the problem. Approximation ratio is only a worst-case bound and pathological instances are usually hard to find. It has been experimentally observed for a variety of approximation algorithms that, on average, the performance is vastly superior than the stated bound. An approximation algorithm can always be refined and tuned to specific classes of instances arising in practice, thereby improving the performance.