Complexity of the Multi-Service Center Problem
Complexity of the Multi-Service Center Problem
复制标题
多服务中心问题的复杂性
DOI：
10.1016/j.tcs.2020.07.021
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
and Yusuke Kobayashi
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Naonori Kakimura;and Yusuke Kobayashi
多服务中心问题是设施选址问题的一个变种。在这个问题中，我们考虑在一个图上定位pfacilities，每个设施提供不同的服务所需的所有顶点。每个顶点产生的成本由到设施点的加权距离之和决定。该问题的目标是最小化所有顶点之间的最大成本。这个问题对于一般的图是NP-难的，而当p是一个固定的常数时，这个问题在多项式时间内是可解的。本文从图类和顶点权的角度对问题的复杂性进行了深入的分析。首先，我们提出了一个多项式时间算法的树时，p是一部分的输入。相反，我们证明了这个问题变得强NP-困难，甚至周期。我们还表明，当顶点被允许有负的权重，问题成为NP-难的路径只有三个顶点和强NP-难的明星。
The multi-service center problem is a variant of facility location problems. In the problem, we consider locatingpfacilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to thepfacilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time whenpis a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees whenpis a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.