一个关于求解k-种产品选址问题的近似算法

摘要：

对于k-种产品工厂选址问题,有如下描述:存在一组客户和一组可以建立工厂的厂址.现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品.在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质.问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品.对于此类问题,优化目标是最小化建厂费用以及运输费用.论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法.

关键词：近似算法、工厂选址、k-种产品

所属期刊栏目：44

分类号：TP301.6(计算技术、计算机技术)

资助基金：湖南省教育厅科研项目05A037

在线出版日期：2008-04-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：97-99