方度量的k层设施选址问题的近似算法
来源：应用数学学报杂志2016年第4期北京时间：
作者：邵嘉婷, 徐大川, 王凤敏
单位：北京工业大学应用数理学院, 北京 100124
摘要：本文中， 我们研究平方度量的k层设施选址问题， 该问题中设施分为k层， 每个顾客都要连接到位于不同层上的k个设施， 顾客与设施以及设施与设施之间的距离是平方度量的. 目标是使得开设费用与连接费用之和最小. 基于线性规划舍入技巧， 我们给出了9-近似算法. 进一步， 我们研究了平方度量的k层软容量设施选址问题， 并给出了线性规划舍入12.2216-近似算法.
关键词：平方度量,k层设施选址,线性规划舍入,软容量,近似算法
基金资助：国家自然科学基金（11371001，11531014）资助项目.
