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

摘要：

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

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

所属期刊栏目：48

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;云南省创新团队项目

在线出版日期：2021-11-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：441-445