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

摘要：

具有等级约束的负载均衡问题是不同类平行机排序问题的一个特殊情形.通过分析该问题的组合性质,得到了一个全范数的2-近似组合算法;当机器数为常数时,给出了一个固定范数下时间复杂性较低的全多项式时间近似方案.这些均在时间复杂性方面改进了之前的结果.

关键词： 排序问题 负载均衡 等级约束 2-近似组合算法 固定范数

作者: 李伟东 李陈筠然 李建平

作者单位: 云南大学,云南省昆明市,650091

会议类型: 国内会议

会议名称: 2015全国理论计算机科学学术年会

会议地点: 金华

会议语种:中文

页码: 1-8

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