Profit-earning facility location
Profit-earning facility location
复制标题
盈利设施位置
DOI：
10.1145/380752.380756
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. Meyerson
中科院分区：
文献类型：
--
作者：
A. Meyerson
为了获得利润，我们考虑开设工厂。我们给定一组需求点，我们必须打开一组设施，使得每一个需求都可以从一个当地设施得到满足，并且在这个过程中获得的总利润最大化。这与之前关于设施选址和k-center问题的研究形成对比，在这些问题中，开设设施需要成本。开设设施所获得的利润是该设施满足的需求量的函数。我们通过在每个地点创建许多不同的可能的设施来模拟利润对需求的依赖，每个设施在开业时都提供一定的利润，并且至少需要一定的需求才能开业。我们的模型捕获了利润可能为正或为负的问题实例，以及没有必要满足每个需求的实例。我们的算法提供了最优的总利润，同时将局域性的定义扩展了一个常数，并违反了一个常数的要求。我们证明，如果没有这个拉伸，问题就会变成NP-Hard逼近。
We consider opening facilities in order to gain a profit. We are given a set of demand points, and we must open some set of facilities such that every demand may be satisfied from a local facility and the total profit gained in this process is maximized. This contrasts with previous work on facility location and k-center problems, where opening a facility incurred a cost. The profit gained by opening a facility is a function of the amount of demand the facility satisfies. We model the dependence of profit on demand by creating many different possible facilities at each location, each of which provides a certain profit if opened and requires at least a certain amount of demand in order to open. Our model captures problem instances where profits may be positive or negative, and also instances where it is not necessary to satisfy every demand. Our algorithms provide the optimum total profit, while stretching the definition of locality by a constant and violating the required demands by a constant. We prove that without this stretch, the problem becomes NP-Hard to approximate.