平方度量的k层设施选址问题的近似算法

• 作者: 徐大川 王凤敏 邵嘉婷
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 平方度量 k层设施选址 线性规划舍入 软容量 近似算法
• 年，卷（期）: 2016,（4）
• 页码范围: 586-597
• 分类号: O221.7
• 语种: 中文

摘要

本文中,我们研究平方度量的k层设施选址问题,该问题中设施分为k层,每个顾客都要连接到位于不同层上的k个设施,顾客与设施以及设施与设施之间的距离是平方度量的.目标是使得开设费用与连接费用之和最小.基于线性规划舍入技巧,我们给出了9-近似算法.进一步,我们研究了平方度量的k层软容量设施选址问题,并给出了线性规划舍入12.2216-近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐大川	北京工业大学应用数理学院	18	30	3.0	4.0
2	邵嘉婷	北京工业大学应用数理学院	3	4	1.0	2.0
3	王凤敏	北京工业大学应用数理学院	4	27	2.0	4.0