lp范数下具有等级约束的负载均衡问题
来源：计算机科学与探索杂志2016年第8期北京时间：
作者：李伟东，李陈筠然，李建平
单位：云南大学，昆明 650091
摘要：具有等级约束的负载均衡问题是不同类平行机排序问题的一个特殊情形。当目标函数为最小化机器负载向量的lp范数时，通过分析该问题的组合性质，利用目标函数的凸性得到了一个全范数2-近似的组合算法；当机器数为常数时，在固定lp范数下，构造一个辅助实例，分析输入实例和辅助实例的最优值之间的关系，利用动态规划算法求出辅助实例的最优解，进一步得到输入实例的一个近似解，其目标函数值与最优值无限接近。这些均在算法的时间复杂性方面改进了之前的结果。
关键词：负载均衡,近似算法,全范数
