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

Semi-online Algorithms for Mixed Ring with Two Nodes

作　　者：肖满 李伟东 XIAO Man;LI Wei-dong(School of Mathematics and Statistics,Yunnan University,Kunming 650504,China)

机构地区：[1]云南大学数学与统计学院,昆明650504

出　　处：《计算机科学》2021年第S02期441-445,共5页Computer Science

基　　金：国家自然科学基金(12071417);云南省创新团队项目。

摘　　要：文中研究了两点混合环上负载均衡问题的两种半在线情形。给定一个两点混合环和若干流量需求,寻找合适的流量运输方式,使得环上的最大负载尽可能地小。当存在一个容量为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.

关 键 词：混合环 半在线算法 缓冲区 竞争比 环负载 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]