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

摘要：

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

关键词：负载均衡、近似算法、全范数

所属期刊栏目：10

分类号：TP301;O223(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.11301466,11461081,61170222;the Natural Science Foundation of Yunnan Province under Grant No.2014FB114

在线出版日期：2016-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1184-1190