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

作     者：肖满 李伟东 XIAO Man;LI Wei-dong

作者机构：云南大学数学与统计学院昆明650504 

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

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2021年第48卷第S02期

页      码：441-445页

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

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.11896/jsjkx.201100153

馆 藏 号：203106266...