工厂地址集中的k-种产品选址问题的近似算法

• 作者: 何晓琼 李荣珩 陈冲
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 近似算法 计算复杂性 工厂选址
• 年，卷（期）: 2010,（8）
• 所属期刊栏目: 工程与应用
• 页码范围: 238-241
• 页数: 4页
• 分类号: TP391
• 字数: 5017字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.08.069

摘要

k一种产品工厂选址问题是:给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要.k一种产品,一个工厂只能为客户提供一种产品.考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离.对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法.对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李荣珩	湖南师范大学数学与计算机学院	11	25	3.0	4.0
2	何晓琼	湖南师范大学数学与计算机学院	1	3	1.0	1.0
3	陈冲	湖南师范大学数学与计算机学院	2	5	2.0	2.0