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

• 作者: 关莉 刘雪明
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 数学
• 关键词: 图均衡 在线算法 竞争比 加权出度 边赋权无向图
• 年，卷（期）: 2021,（2）
• 所属期刊栏目: 算法与复杂性
• 页码范围: 28-31,61
• 页数: 5页
• 分类号: O224
• 语种: 中文
• 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的最优算法.