Linear programming based approximation algorithms for optimization problems

基于线性规划的优化问题近似算法

• 批准号: 262126-2009
• 负责人: Gaur, Daya
• 金额: $ 1.38万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2009
• 资助国家: 加拿大
• 起止时间: 2009-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=426976
• 关键词: Linear; programming; based; approximation; algorithms

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.

近似算法是一个优雅的形式框架，用于处理本质上困难的优化问题。优化问题的近似算法在多项式时间内产生一个可行解，该解位于问题的每个实例的最佳解的恒定乘法因子内。近似比率只是最坏情况的界限，并且病理实例通常很难找到。通过实验观察到，各种近似算法的平均性能远远优于规定的范围。近似算法始终可以针对实践中出现的特定实例类别进行改进和调整，从而提高性能。