关于单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q的一个注记

• 作者: 李剑秋 罗文昌
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 两个客户 竞争排序 多个维护 近似算法
• 年，卷（期）: 2011,（1）
• 页码范围: 73-80
• 分类号: O221.7
• 字数: 5257字
• 语种: 中文

摘要

研究了单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q,证明了该问题与问题1|MAi|∑wjcj及问题1|hi,pmtn|∑wjcj之间是相互等价的.对wj=pj时的特殊情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对wj任意的一般情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1||∑wAjcAj:fBmax≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1||∑wAjcAj:∑wBjcBj ≤ Q具有多项式时间近似方案(PTAS).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗文昌	宁波大学理学院	13	41	4.0	6.0
3	李剑秋	浙江工商大学杭州商学院	6	12	2.0	3.0