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

Approximation Algorithms for the Squared Metric k-Level Facility Location Problem

作　　者：邵嘉婷[1] 徐大川[1] 王凤敏[1] 

机构地区：[1]北京工业大学应用数理学院,北京100124

出　　处：《应用数学学报》2016年第4期586-597,共12页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11371001;11531014)资助项目

摘　　要：本文中,我们研究平方度量的k层设施选址问题,该问题中设施分为k层,每个顾客都要连接到位于不同层上的k个设施,顾客与设施以及设施与设施之间的距离是平方度量的.目标是使得开设费用与连接费用之和最小.基于线性规划舍入技巧,我们给出了9-近似算法.进一步,我们研究了平方度量的k层软容量设施选址问题,并给出了线性规划舍入12.2216-近似算法.In this paper, we study the squared metric k-level facility location problem where the facilities are on k-level. The objective is to minimize the sum of the opening cost, the connection cost. Using the LP-rounding techniques, we then propose an approximation algorithm and obtain the approximation ratio of 9. Furthermore, we study the squared metric k-level soft capacitied facility location problem. Using the LP-rounding techniques, we then propose an approximation algorithm and obtain the approximation ratio of 12.2216.

关 键 词：平方度量 k层设施选址 线性规划舍入 软容量 近似算法 

分 类 号：O221.7[理学—运筹学与控制论]