文章基本信息

标题：Complexity of the Multi-Service Center Problem
本地全文：下载
作者：Takehiro Ito ; Naonori Kakimura ; Yusuke Kobayashi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：92
页码：48:1-48:12
DOI：10.4230/LIPIcs.ISAAC.2017.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities 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 the p facilities. 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 when p is 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 when p is 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.
关键词：facility location; graph algorithm; multi-service location