NP问题的LP近似算法及不可近似性

• 作者: 黄岗
• 来源期刊: 电子测试
• 学科: 经济
• 关键词: 非确定多项式 线性规划 近似算法 不可近似性
• 年，卷（期）: 2013,（10）
• 页码范围: 234-235
• 页数: 2页
• 分类号: F830.4|F224
• 字数: 2601字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄岗		9	45	3.0	6.0