限制设施选址问题的近似算法  

Approximation algorithm for limited facility location problem

作　　者：刘玉堂[1] 方奇志[1] 

机构地区：[1]中国海洋大学数学科学学院,山东青岛266100

出　　处：《计算机工程与科学》2013年第4期111-114,共4页Computer Engineering & Science

摘　　要：提出了设施选址问题的一个新变体—限制设施选址问题,给出了一个基于随机线性规划舍入的近似算法,并分析了算法的近似度。The paper presented an approximation algorithm for the Limited Facility Location problem （LFL）, which is a new variant of the classical Uncapacitated Facility Location problem（UFL）. The al- gorithm is based on randomized LP rounding, and its approximation ratio was analyzed.

关 键 词：设施选址问题 近似算法 随机线性规划舍入 

分 类 号：O224[理学—运筹学与控制论]