应用数学学报

作者：李小玮, 成夏炎, 李荣珩

单位：1. 计算与随机数学教育部重点实验室, 复杂系统的控制与优化湖南省高校重点实验室, 湖南师范大学数学与统计学院, 长沙 410081;<br>2. 湖南第一师范大学数学与统计学院, 长沙 410205

关键词：近似算法,设施选址,原始对偶

本文我们研究了设施建设费用为零时的带线性惩罚的$k$-种产品设施选址问题与带次模惩罚的$k$-种产品设施选址问题.在带线性惩罚的$k$-种产品设施选址问题中,每一客户均对应一定的惩罚费用,目标是选择一个开设的设施集合,将一部分客户连接到开设的设施,使得这些客户对$k$种产品的需要均得到满足,同时对另一部分客户进行惩罚,并使得客户连接费用与客户惩罚费用之和最小.针对该问题特殊结构,当$k\geq 3$时我们得到了$\frac{3k}{2}-\frac{3}{2}$ 近似算法.在带次模惩罚的$k$-种产品设施选址问题中,客户的每个子集都对应一定的次模惩罚费用,我们给出了该问题的数学规划模型,结合问题的次模性,利用原始对偶算法,当$k\geq 3$ 时得到了$\frac{3k}{2}-\frac{3}{2}$ 近似算法.

来源：2022年第3期

《应用数学学报》期刊编辑部

查看应用数学学报杂志2022年第3期