-
题名带次模惩罚的优先设施选址问题的近似算法
被引量：1
- 1
-
-
作者
王颖
王凤敏
徐大川
徐文青
-
机构
太原工业学院理学系
北京工业大学应用数理学院
加州州立大学长滩分校数学与统计系
-
出处
《运筹学学报》
CSCD
北大核心
2015年第2期1-14,共14页
-
基金
国家自然科学基金(No.11371001)
-
文摘
研究带次模惩罚的优先设施选址问题,每个顾客都有一定的服务水平要求,开设的设施只有满足了顾客的服务水平要求,才能为顾客提供服务,没被服务的顾客对应一定的次模惩罚费用.目标是使得开设费用、连接费用与次模惩罚费用之和最小.给出该问题的整数规划、线性规划松弛及其对偶规划.基于原始对偶和贪婪增广技巧,给出该问题的两个近似算法,得到的近似比分别为3和2.375.
-
关键词
次模惩罚
优先设施选址
原始对偶
贪婪增广
近似算法
-
Keywords
submodular penalties, priority facility location, primal-dual, greedy augmentation, approximation algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-
