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