两点混合环上的半在线算法

Semi-online Algorithms for Mixed Ring with Two Nodes

文中研究了两点混合环上负载均衡问题的两种半在线情形。给定一个两点混合环和若干流量需求,寻找合适的流量运输方式,使得环上的最大负载尽可能地小。当存在一个容量为K的缓冲区时,证明了该半在线情形的下界为4/3。特别地,当K=1时,证明了下界为3/2,并给出了一个竞争比至多为8/5的半在线算法。当所有流的需求之和已知时,设计了一个竞争比为3/2的最优半在线算法。

Two semi-online scenarios of load balancing problem on a two-point mixed ring are studied.This paper gives a two-point mixed ring and several flow requests,finds a suitable flow transportation method to make the maximum load on the ring as small as possible.When there is a buffer with a capacity of K,the lower bound of 4/3 is given.In particular,when K=1,a lower bound of 3/2 is given,and a semi-online algorithm with a competitive ratio of at most 8/5 is given.When the sum of all flow demands is known,an optimal semi-online algorithm with a competitive ratio of 3/2 is designed.