2021-06-22T15:06:05Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001910332020-04-01T00:33:29Z01164:02592:09368:09546
On the Multi-Service Center ProblemOn the Multi-Service Center Problemenghttp://id.nii.ac.jp/1001/00190945/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=191033&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of JapanGraduate School of Information Sciences, Tohoku UniversityDepartment of Mathematics, Keio UniversityResearch Institute for Mathematical Sciences, Kyoto UniversityTakehiro, ItoNaonori, KakimuraYusuke, KobayashiThe 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-1692142018-08-272188-85662018-08-23