两类推广的动态设施选址问题的近似算法

摘要

本论文主要研究带惩罚的动态设施选址问题及软容量约束的动态设施选址问题.由于该问题是NP困难的,我们考虑其近似算法的设计与分析.论文有如下两部分内容:
　　 第一部分研究带惩罚的动态设施选址问题.在该问题中给定若干时段,不同时段内设施的开放费用、用户的需求及连接费用不一定相同,而且允许用户的需求不被满足,但不满足的部分要有惩罚.利用原始对偶技巧,我们给出了该问题的3-近似算法.再运行贪婪增加程序后,近似比改进到1.8526.
　　 第二部分研究软容量约束的动态设施选址问题.在该问题中每一个设施都是有软容量限制的.利用拉格朗日松弛技巧,我们给出了该问题的6-近似算法.运行贪婪增加程序后,近似比改进到3.7052.

目录

文摘

英文文摘

第1章 绪论

1.1 研究背景

1.2 问题介绍

1.3 国内外研究现状

1.4 主要结果

1.5 论文结构

第2章 带惩罚的动态设施选址问题

2.1 DFLPWP的原始对偶算法

2.2 原始对偶算法的理论分析

2.3 改进的算法及其分析

2.4 本章小结

第3章 软容量约束的动态设施选址问题

3.1 算法

3.2 算法分析

3.3 改进的算法及其分析

3.4 本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢