以线性规划(linear program,LP)对非确定多项式(Non-Deterministic Polynomial,NP)问题的近似求解算法进行了讨论。首先,介绍了LP求解中的基本概念与相关定理;之后,从LP求最优解后做变换和利用primal和dual的经典技术两个思路对线性规划近似算法进行了详细介绍;最后,对NP问题中的不可近似性进行了分析,并讨论了各个算法的特点。
科研之友
微信
新浪微博
Facebook
分享链接
