• 论文 • 上一篇    下一篇

软容量约束的动态设施选址问题的近似算法

姜春艳1,李改弟2   

  1. 1. 武警学院基础部, 廊坊 065000;北京工业大学应用数理学院, 北京 100124; 2. 北京工业大学应用数理学院, 北京 100124
  • 收稿日期:2009-09-14 出版日期:2012-04-25 发布日期:2012-07-06

姜春艳,李改弟. 软容量约束的动态设施选址问题的近似算法[J]. 系统科学与数学, 2012, 32(4): 476-484.

JIANG Chunyan,LI Gaidi. AN APPROXIMATION ALGORITHM FOR THE SOFT-CAPACITATED DYNAMIC FACILITY LOCATION PROBLEM[J]. Journal of Systems Science and Mathematical Sciences, 2012, 32(4): 476-484.

AN APPROXIMATION ALGORITHM FOR THE SOFT-CAPACITATED DYNAMIC FACILITY LOCATION PROBLEM

JIANG Chunyan1,LI Gaidi2   

  1. 1. Basic Courses Teaching Department, The Armed Police Academy, Langfang 065000;College of Applied Sciences, Beijing University of Technology,Beijing 100124 ; 2. College of Applied Sciences, Beijing University of Technology, Beijing 100124
  • Received:2009-09-14 Online:2012-04-25 Published:2012-07-06
虑软容量约束的动态设施选址问题. 假设设施的开放费用及连接费用都与时间有关, 而且每一个设施均有容量约束. 对此问题给出了第一个近似比为$6$的原始对偶(组合)算法. 运行贪婪增加程序后, 近似比进一步改进到$3.7052$.
The paper considers the soft-capacitated dynamic facility location problem (SCDFLP). It is assumed that the facility open cost and the connection cost are time-dependent, and each facility has a capacity. We present the first primal-dual (combinatorial) approximation algorithm for the problem with approximation ratio 6 . We further improve the approximation ration to 3.7052 using greedy augmentation scheme.

MR(2010)主题分类: 

()
[1] 吴波, 施敏加, 李淑宇, 杨绍波, 左其尚. $2$-Lee 重量 $\mathbb{Z}_p\mathbb{Z}_p[u]$-加性码[J]. 系统科学与数学, 2021, 41(9): 2678-2686.
[2] 曲国华, 许岩, 曲卫华, 张强. 基于区间对偶犹豫模糊信息双向投影技术的双边公平匹配决策方法[J]. 系统科学与数学, 2021, 41(5): 1256-1275.
[3] 胡建,曹喜望. 自共轭互反多项式的推广[J]. 系统科学与数学, 2020, 40(8): 1507-1516.
[4] 李春华,曲国华,曲卫华,周海昇,张强. 考虑信息源相关的对偶犹豫模糊多属性绿色行为决策方法[J]. 系统科学与数学, 2020, 40(7): 1224-1241.
[5] 杨艺. 基于全序关系与A-DHFHW算子的DHFMAGDM方法及其应用[J]. 系统科学与数学, 2020, 40(5): 871-890.
[6] 袁文红. 伽罗瓦内积下LCD常循环码和LCD MDS码的研究[J]. 系统科学与数学, 2018, 38(12): 1464-1476.
[7] 丁恒,李延来. 弧$k/n(G)$与节点$k/n(G)$网络模型可靠性估计的对偶变量蒙特罗洛方法[J]. 系统科学与数学, 2018, 38(1): 86-100.
[8] 李科科,彭再云,赵勇,李小兵. 含参原始与对偶弱向量近似平衡问题的稳定性[J]. 系统科学与数学, 2017, 37(7): 1605-1619.
[9] 杨玉红,唐莉萍. 非光滑半无限多目标优化问题的对偶性[J]. 系统科学与数学, 2017, 37(7): 1633-1645.
[10] 李兰强,刘丽. 环${Z}_{ 4}+{u}{Z}_{ 4}$上一类重根常循环码[J]. 系统科学与数学, 2017, 37(3): 870-881.
[11] 方东辉. 复合优化问题的Fenchel对偶[J]. 系统科学与数学, 2017, 37(2): 528-536.
[12] 方东辉,王梦丹. 锥约束复合优化问题的Lagrange对偶[J]. 系统科学与数学, 2017, 37(1): 203-211.
[13] 吴霜,舒兰,莫智文. 一个部分信息的倒向随机时滞系统的最优控制问题[J]. 系统科学与数学, 2016, 36(12): 2172-2178.
[14] 黄炎,开晓山,宛金龙.  环$\mathbb{Z}_{p^2}$上的循环自正交码的构造[J]. 系统科学与数学, 2016, 36(12): 2473-2480.
[15] 张玉忠,苗翠霞. 机器有使用限制的混合恶化排序问题的复杂性[J]. 系统科学与数学, 2015, 35(6): 685-694.
阅读次数
全文


摘要