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.

近似算法是一个优雅的形式化框架，用于处理本质上困难的优化问题。优化问题的近似算法在多项式时间内产生可行解，该可行解在问题的每个实例的最优解的常数乘法因子内。近似比只是一个最坏情况的界限，病理情况通常很难找到。它已被实验观察到的各种近似算法，平均而言，性能大大优于上级比所述的界限。近似算法总是可以针对实践中出现的特定类别的实例进行细化和调整，从而提高性能。