带次模惩罚的优先设施选址问题的近似算法

作者：王颖; 王凤敏; 徐大川; 徐文青

来源：运筹学学报, 2015, 19(02): 1-14.

DOI：10.15960/j.cnki.issn.1007-6093.2015.02.001

• 次模惩罚
• 优先设施选址
• 原始对偶
• 贪婪增广
• 近似算法

研究带次模惩罚的优先设施选址问题,每个顾客都有一定的服务水平要求,开设的设施只有满足了顾客的服务水平要求,才能为顾客提供服务,没被服务的顾客对应一定的次模惩罚费用.目标是使得开设费用、连接费用与次模惩罚费用之和最小.给出该问题的整数规划、线性规划松弛及其对偶规划.基于原始对偶和贪婪增广技巧,给出该问题的两个近似算法,得到的近似比分别为3和2.375.

• 出版日期2015
• 单位数理学院; 北京工业大学; 太原工业学院