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

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

作　　者：姜春艳[1,2] 李改弟[2] 

机构地区：[1]武警学院基础部,廊坊065000 [2]北京工业大学应用数理学院,北京100124

出　　处：《系统科学与数学》2012年第4期476-484,共9页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(11071268);北京市教育委员会科技计划面上项目(KM201210005033)资助课题

摘　　要：考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为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.

关 键 词：软容量约束动态设施选址问题 对偶 近似算法 

分 类 号：O224[理学—运筹学与控制论]