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

• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 动态设施选址问题 线性规划 近似算法
• 年，卷（期）: 2009,（6）
• 页码范围: 988-996
• 页数: 9页
• 分类号: O221.7
• 字数: 5196字
• 语种: 中文

摘要

本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第-个近似比为1.8526的原始对偶(组合)算法.