A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
复制标题
轻超边图平衡的组合逼近算法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sebastian Ott
中科院分区：
文献类型：
--
作者：
Chien;Sebastian Ott
限制指派（R）中的最大跨度极小化问题|pij {pj，∞}| Cmax）是机器调度领域的经典问题。在1990年的一篇里程碑式的论文中，Lenstra，Shmoys和Tardos给出了一个2-近似算法，并证明了除非P=NP，否则该问题不能在1.5内近似。问题的上界和下界在25年的时间里基本上没有得到改进，尽管最近在一些特殊情况下进行了一些显著的成功尝试[2，3，13]。在本文中，我们考虑一个特殊的情况称为图平衡轻超边，重的工作可以分配给最多两台机器，而轻的工作可以分配给任何数量的机器。对于这种情况下，我们提出的算法的近似比严格优于2。·两个作业大小：假设轻作业的权重为w，重作业的权重为W，且w < W。我们给出了一个1.5近似算法（注意，当前的1.5下限是在更严格的设置中建立的[1，4]）。事实上，根据w和W的具体值，有时我们的算法保证低于1.5的近似比。·任意工作大小：假设W是给定的最大权重，重作业的权重在（βW，W]的范围内，其中4/7 ≤ β < 1，轻作业的权重在（0，βW]的范围内。我们提出了一个（5/3 + β/3）-近似算法。我们的算法是纯粹的组合，而不需要解决一个线性规划所需的大多数其他已知的方法。
Makespan minimization in restricted assignment (R|pij ϵ {pj, ∞}|Cmax) is a classical problem in the field of machine scheduling. In a landmark paper in 1990 [9], Lenstra, Shmoys, and Tardos gave a 2-approximation algorithm and proved that the problem cannot be approximated within 1.5 unless P=NP. The upper and lower bounds of the problem have been essentially unimproved in the intervening 25 years, despite several remarkable successful attempts in some special cases of the problem [2, 3, 13] recently. In this paper, we consider a special case called graph-balancing with light hyper edges, where heavy jobs can be assigned to at most two machines while light jobs can be assigned to any number of machines. For this case, we present algorithms with approximation ratios strictly better than 2. Specifically, • Two job sizes: Suppose that light jobs have weight w and heavy jobs have weight W, and w < W. We give a 1.5-approximation algorithm (note that the current 1.5 lower bound is established in an even more restrictive setting [1, 4]). Indeed, depending on the specific values of w and W, sometimes our algorithm guarantees sub-1.5 approximation ratios. • Arbitrary job sizes: Suppose that W is the largest given weight, heavy jobs have weights in the range of (βW, W], where 4/7 ≤ β < 1, and light jobs have weights in the range of (0, βW]. We present a (5/3 + β/3)-approximation algorithm. Our algorithms are purely combinatorial, without the need of solving a linear program as required in most other known approaches.