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

doi:10.12341/jssms11866

系统科学与数学 ›› 2012, Vol. 32 ›› Issue (4): 476-484.DOI: 10.12341/jssms11866

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

姜春艳¹，李改弟²

1. 武警学院基础部, 廊坊 065000;北京工业大学应用数理学院, 北京 100124; 2. 北京工业大学应用数理学院, 北京 100124

收稿日期:2009-09-14 出版日期:2012-04-25 发布日期:2012-07-06

PDF ( 676 ) 引用被引次数 ( 1 )

姜春艳，李改弟. 软容量约束的动态设施选址问题的近似算法[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 Chunyan¹，LI Gaidi²

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)主题分类:

90C27

分享此文:

[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.

阅读次数

全文

摘要