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

J4 ›› 2013, Vol. 35 ›› Issue (4): 111-114.

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

刘玉堂，方奇志

（中国海洋大学数学科学学院，山东青岛 266100）

收稿日期:2012-05-16 修回日期:2012-08-20 出版日期:2013-04-25 发布日期:2013-04-25

Approximation algorithm for limited facility location problem

LIU Yutang，FANG Qizhi

（School of Mathematical Sciences,Ocean University of China,Qingdao 266100,China）

Received:2012-05-16 Revised:2012-08-20 Online:2013-04-25 Published:2013-04-25

摘要/Abstract

摘要：

提出了设施选址问题的一个新变体—限制设施选址问题，给出了一个基于随机线性规划舍入的近似算法，并分析了算法的近似度。

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

Abstract:

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 algorithm is based on randomized LP rounding, and its approximation ratio was analyzed.

Key words: facility location problem;approximation algorithm;randomized LP rounding

刘玉堂，方奇志. 限制设施选址问题的近似算法[J]. J4, 2013, 35(4): 111-114.

LIU Yutang，FANG Qizhi. Approximation algorithm for limited facility location problem [J]. J4, 2013, 35(4): 111-114.

[1]	钟昊, 陈卫东. 一般图中的最小概要表示集问题[J]. 计算机工程与科学, 2023, 45(01): 113-118.
[2]	关莉，冯彦雪. 混合环上带惩罚费用的负载平衡问题[J]. 计算机工程与科学, 2019, 41(11): 1949-1953.
[3]	程佳乐，李伟东. 具有树和路约束的平行机排序问题[J]. 计算机工程与科学, 2018, 40(12): 2273-2279.
[4]	颜庆，张鹏. 社会网络中的影响力最大化问题[J]. J4, 2015, 37(02): 263-268.
[5]	王敏，吴中博，徐德刚，屈俊峰，吴钊. 基于预测模型的传感器网络近似数据采集算法[J]. J4, 2014, 36(11): 2148-2152.
[6]	杨宪泽,肖明. 一种混合式机器翻译方法的分析研究[J]. J4, 2012, 34(2): 168-171.
[7]	王刚，骆志刚，李聪，黄旭慧. 近似算法之测度视角[J]. J4, 2012, 34(11): 83-90.
[8]	范克磊, 栾峻峰. 高维空间球集覆盖问题的改进1+ε近似算法[J]. J4, 2010, 32(1): 44-46.
[9]	唐晋韬王挺. 复杂社会网络的介数性质近似计算方法研究[J]. J4, 2008, 30(12): 9-14.
[10]	幸冬梅[1,2]. 一类弱支配集问题的近似算法[J]. J4, 2008, 30(12): 97-101.
[11]	丁玲玲方奇志. 控制集与部分控制集问题的原始-对偶算法[J]. J4, 2008, 30(12): 102-104.
[12]	伍勇安殷建平李敏. 无线传感器网络连通忌覆盖问题及其解决方案综述[J]. J4, 2008, 30(11): 155-158.
[13]	栾峻峰范克磊鲍海峰. 高维空间球体的k-中心聚类问题[J]. J4, 2008, 30(10): 103-104.
[14]	凤旺森[1,2] 屈婉玲[1,2] 王捍贫[1,2] 张立昂[1,2]. 无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法[J]. J4, 2008, 30(10): 21-23.
[15]	杨宪泽雷开彬吴守宪张上游宁爱华. 一种句型转换和近似机器翻译方法及算法[J]. J4, 2005, 27(11): 66-68.