论文标题
在线无关机机负载平衡和通用流程
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
论文作者
论文摘要
我们考虑在线无关的机器负载平衡问题与追索权，其中允许算法重新分配先前的工作。我们给出了$（2+ε）$ - 竞争算法，以解决$o_ε（\ log n）$摊销的每份工作。这是第一个$ o（1）$ - 具有合理追索问题的问题的竞争算法，竞争比率几乎与长期最著名的离线近似保证相匹配。我们还显示了一个$ O（\ log \ log n/\ log \ log \ log n）$ - 与$ o（1）$ amortized suckirese有关的问题的竞争算法。先前工作的最著名界限是$ O（\ log \ log n）$ - 竞争性算法，$ O（1）$（1）由于[GKS14]而引起的$ O（1）$（1）$ o（1）$（1）$（1）$（1）$ o（\ log \ log n）$（gks14]，对于限制分配模型的特殊情况。 在此过程中，我们设计了一种用于在线通用网络流问题（也称为收益的网络流问题）的算法。在问题中，网络中的任何边缘$ uv $都具有增益参数$γ_{uv}> 0 $和$θ$ - 从$ u $的side发送的流量，从$ u $的方面发送$γ_{uv}θ$ flow $ v $'then的$γ_{uv}θ$。在在线问题中，有一个水槽，消息来源逐一出现。来源到达后，我们需要从源发送1个单位流。如果我们更改边缘的流动值，就会发生追索权。我们给在线算法，以解决$ o（1/ε）$ o（1/ε）$乘以该实例的最佳成本的问题，其功能由$ \ frac {1} {1+ε} $。 $（1+ε）$ - 因子在[GKS14]的相应$（2+ε）$上进行改进，该因素仅适用于普通网络流问题。作为立即推论，我们还为在线$ b $的问题提供了改进的算法以及重新分配成本。
We consider the online unrelated-machine load balancing problem with recourse, where the algorithm is allowed to re-assign prior jobs. We give a $(2+ε)$-competitive algorithm for the problem with $O_ε(\log n)$ amortized recourse per job. This is the first $O(1)$-competitive algorithm for the problem with reasonable recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an $O(\log\log n/\log\log\log n)$-competitive algorithm for the problem with $O(1)$ amortized recourse. The best-known bounds from prior work are $O(\log\log n)$-competitive algorithms with $O(1)$ amortized recourse due to [GKS14], for the special case of the restricted assignment model. Along the way, we design an algorithm for the online generalized network flow problem (also known as network flow problem with gains) with recourse. In the problem, any edge $uv$ in the network has a gain parameter $γ_{uv} > 0$ and $θ$-units of flow sent across $uv$ from $u$'s side becomes $γ_{uv} θ$ units of flow on the $v$'th side. In the online problem, there is one sink, and sources come one by one. Upon arrival of a source, we need to send 1 unit flow from the source. A recourse occurs if we change the flow value of an edge. We give an online algorithm for the problem with recourse at most $O(1/ε)$ times the optimum cost for the instance with capacities scaled by $\frac{1}{1+ε}$. The $(1+ε)$-factor improves upon the corresponding $(2+ε)$-factor of [GKS14], which only works for the ordinary network flow problem. As an immediate corollary, we also give an improved algorithm for the online $b$-matching problem with reassignment costs.
