路上最大最小图均衡问题的在线算法

作者：关莉; 刘雪明

来源：华中科技大学学报(自然科学版)科技大学, 2021, 49(02): 28-61.

DOI：10.13245/j.hust.210203

• 图均衡
• 在线算法
• 竞争比
• 加权出度
• 边赋权无向图

研究路上最大最小图均衡问题的在线情形。对于边权不可分的情形,在路的长度为2,且总权重W已知或最大权重wmax已知的情况下,该问题没有有限的竞争比。对于边权可分的情形,当n≥3时,无论总权重W是否已知,该问题具有相同的竞争比下界,当n=2时,总权重W是否已知将令问题具有不同的竞争比下界。当n=2且W已知时,设计了一个最优算法;当n=2且W未知时,设计了一个竞争比为4/3的最优算法;当n=3时,设计了一个竞争比为3/2的最优算法;当n=4时,设计了一个竞争比为3/2的最优算法;当n≥5时,设计了一个竞争比为2的最优算法。