New Algorithms for 1-D Facility Location and Path Equipartition Problems
New Algorithms for 1-D Facility Location and Path Equipartition Problems
复制标题
一维设施位置和路径均分问题的新算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Haitao Wang
中科院分区：
文献类型：
--
作者：
D. Chen;Haitao Wang
研究了一维设施选址问题。给定真实的线路上的n个客户的集合，每个客户具有在其位置处设置设施的成本和整数k，我们寻求找到至多k个客户来设置设施以服务所有n个客户，使得设施设置和服务运输的总成本最小化。我们考虑几个问题的变化，包括k-中位数和k-覆盖率和线性模型。我们还研究了一个相关的路径均分问题：给定一个顶点加权路径和一个整数k，删除k-1条边，使得到的k个子路径的权重尽可能相等。基于新的问题建模和观察，我们提出了改进的算法，这些问题在以前的工作。
We study the one-dimensional facility location problems. Given a set of n customers on the real line, each customer having a cost for setting up a facility at its position, and an integer k, we seek to find at most k of the customers to set up facilities for serving all n customers such that the total cost for facility set-up and service transportation is minimized. We consider several problem variations including k-median and k-coverage and a linear model. We also study a related path equipartition problem: Given a vertex-weighted path and an integer k, remove k-1 edges so that the weights of the resulting k sub-paths are as equal as possible. Based on new problem modeling and observations, we present improved algorithms for these problems over the previous work.