论文摘要
在过去的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
相关论文文献
- [1].宽带微带线3dB混合环设计[J]. 数码世界 2017(05)
- [2].宽带3dB混合环基本原理的研究[J]. 微型机与应用 2011(07)
- [3].具有谐波抑制的小型化混合环耦合器设计[J]. 现代电子技术 2017(21)
- [4].基于波导混合环的毫米波宽带功率分配/合成器的设计[J]. 微波学报 2015(S2)
- [5].一种小型化混合环及基于它的混频器设计[J]. 固体电子学研究与进展 2015(01)
- [6].梳棉机混合环自调匀整系统的PID控制与仿真[J]. 工业控制计算机 2014(02)
- [7].自调匀整技术在棉纺中的应用[J]. 现代纺织技术 2011(05)
- [8].二进制宽带毫米波合成器设计与分析[J]. 火控雷达技术 2016(02)
- [9].基于混合环功分/功合网络宽带微波固态功率放大器的设计与实现[J]. 甘肃科技 2014(22)
- [10].互联网混合环保思维“入侵”Zipcar的13年[J]. 中国汽车界 2012(03)
- [11].空间分离的路径纠缠微波信号制备方案[J]. 空军工程大学学报(自然科学版) 2017(04)