混合环上带惩罚费用的负载平衡问题

• 作者: 关莉 冯彦雪
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 近似算法 混合环负载 惩罚费用
• 年，卷（期）: 2019,（11）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 1949-1953
• 页数: 5页
• 分类号: TP301.6
• 字数: 4988字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2019.11.007

摘要

在过去的20多年里,环负载平衡问题得到了广泛的研究.带惩罚费用的环负载平衡问题是环负载平衡问题的推广形式,在无向环和有向环上有一些研究结果.提出了带惩罚费用的混合环负载平衡问题,对于给定的混合环C和点对集,每1个点对rj都有1个流量dj和1个惩罚费用pj,当点对rj被接收时,其流量可以沿环上的顺时针路和逆时针路进行运输,点对rj也可以被拒绝,此时将产生惩罚费用pj,目标是使得环C上连接边的最大负载和惩罚费用之和达到最小.在流量可分的情况下,利用线性规划取整技巧,给出了1个2-近似算法,进一步地,利用随机取整技巧,得到1个更好的近似算法,近似比为1.58.类似地,在流量不可分的情况下,给出了1个3-近似算法和1个(1.58+ε)-近似算法,其中ε>0是一个固定的常数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	关莉	云南大学数学与统计学院	7	44	3.0	6.0
2	冯彦雪	云南大学数学与统计学院	1	0	0.0	0.0