在过去的20多年里,环负载平衡问题得到了广泛的研究。带惩罚费用的环负载平衡问题是环负载平衡问题的推广形式,在无向环和有向环上有一些研究结果。提出了带惩罚费用的混合环负载平衡问题,对于给定的混合环C和点对集,每1个点对rj都有1个流量dj和1个惩罚费用pj,当点对rj被接收时,其流量可以沿环上的顺时针路和逆时针路进行运输,点对rj也可以被拒绝,此时将产生惩罚费用pj,目标是使得环C上连接边的最大负载和惩罚费用之和达到最小。在流量可分的情况下,利用线性规划取整技巧,给出了1个2-近似算法,进一步地,利用随机取整技巧,得到1个更好的近似算法,近似比为1.58。类似地,在流量不可分的情况下,给出了1个3-近似算法和1个（1.58+ε）-近似算法,其中ε>0是一个固定的常数。
类型: 期刊论文
作者: 关莉,冯彦雪
关键词: 近似算法,混合环负载,惩罚费用
来源: 计算机工程与科学 2019年11期
年度: 2019
分类: 信息科技,基础科学
专业: 数学
单位: 云南大学数学与统计学院
基金: 国家自然科学基金(11761078,11861075),云南省教育厅科学研究基金(2017ZZX235),云南省高校计算理论与应用科技创新团队建设项目(云教高[2018]134号),云南省科技厅-云南大学联合基金重点项目(2018FY001(-014))
分类号: O221.1;O153.3
页码: 1949-1953
总页数: 5
文件大小: 208K
下载量: 26
本文来源: https://www.lunwen66.cn/article/badbbcf9246fddb12a60c07e.html