lp范数下具有等级约束的负载均衡问题

• 作者: 李伟东 李建平 李陈筠然
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 负载均衡 近似算法 全范数
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 理论与算法
• 页码范围: 1184-1190
• 页数: 7页
• 分类号: TP301|O223
• 字数: 5795字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1507046

摘要

具有等级约束的负载均衡问题是不同类平行机排序问题的一个特殊情形.当目标函数为最小化机器负载向量的lp范数时,通过分析该问题的组合性质,利用目标函数的凸性得到了一个全范数2-近似的组合算法;当机器数为常数时,在固定‘范数下,构造一个辅助实例,分析输入实例和辅助实例的最优值之间的关系,利用动态规划算法求出辅助实例的最优解,进一步得到输入实例的一个近似解,其目标函数值与最优值无限接近.这些均在算法的时间复杂性方面改进了之前的结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建平		14	64	3.0	7.0
2	李伟东		13	35	3.0	5.0
3	李陈筠然		1	1	1.0	1.0