带惩罚的动态设施选址问题的近似算法  

An Approximation Algorithm for the Dynamic Facility Location Problem with Penalties

作　　者：姜春艳[1,2] 徐大川[2] 

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

出　　处：《应用数学学报》2009年第6期988-996,共9页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(60773185)资助项目

摘　　要：本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第一个近似比为1.8526的原始对偶(组合)算法.In this paper, we study the dynamic facility location problem with penalties. In this problem, we assume that the facility cost, the service cost, and the demand and penalty of each client maybe different at each time period. At each time period, a client can be served by an opened facility or rejected by paying a penalty. We obtain the first （combinatorial） approximation algorithm with a performance factor of 1.8526 for this problem.

关 键 词：动态设施选址问题 线性规划 近似算法 

分 类 号：O221.7[理学—运筹学与控制论]