http://swrc.ontoware.org/ontology#TechnicalReport
On the Multi-Service Center Problem
en
Graduate School of Information Sciences, Tohoku University
Department of Mathematics, Keio University
Research Institute for Mathematical Sciences, Kyoto University
Takehiro Ito
Naonori Kakimura
Yusuke Kobayashi
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.
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.
AN1009593X
研究報告アルゴリズム（AL）
2018-AL-169
2
1-4
2018-08-27
2188-8566