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

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

限制性多源点偏心距增广问题

给定一个赋权图G=(V,E;w,c)以及图G的一个支撑子图G_(1)=(V,E_(1)),这里源点集合S={s_(1),s_(2),…,s_(k)}?V,权重函数w:E→R^(+),费用函数c:E\E_(1)→Z^(+)和一个正整数B,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下:(1)限制性多源点最小偏心距增广问题是要寻找一个边子集E_(2)■E\E_(1),满足约束条件c(E_(2))≤B,目标是使得子图G_(1)∪E_(2)上源点集S中顶点偏心距的最小值达到最小;(2)限制性多源点最大偏心距增广问题是要寻找一个边子集E_(2)■E\E_(1),满足约束条件c(E_(2))≤B,目标是使得子图G_(1)∪E_(2)上源点集S中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。