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.