问题1|dj =d|Σwj Tj 的一个全多项式近似方案

• 作者: 张喆 李文华
• 来源期刊: 数学杂志
• 学科: 数学
• 关键词: 相同工期 加权总误工 全多项式近似方案
• 年，卷（期）: 2015,（4）
• 页码范围: 1005-1011
• 页数: 7页
• 分类号: O221.7
• 字数: 4674字
• 语种: 中文

摘要

本文对具有相同工期的单机最小化加权总误工问题进行了讨论。利用强NP -困难问题1kΣwjTj 的一个O(n2)时间的近似算法，把该算法得到的目标值作为问题1|dj =d|ΣwjTj 的一个上界，对问题1|dj =d|Σwj Tj 给出全多项式近似方案(FPTAS)。已知问题1|dj =d|Σwj Tj 是一般意义下的NP-困难问题，并且已经有人对该问题给出了拟多项式时间算法，本文对已有结果进行了扩充。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张喆	中原工学院理学院	17	37	3.0	5.0
2	李文华	郑州大学数学系	17	50	4.0	5.0