2026-07-22T16:58:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8253 2024-03-06T10:41:51Z ddc:004 open_access

Complexity of the Multi-Service Center Problem Ito, Takehiro Kakimura, Naonori Kobayashi, Yusuke facility location graph algorithm multi-service location 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takehiro Ito and Naonori Kakimura and Yusuke Kobayashi 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.48 urn:nbn:de:0030-drops-82536 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.48 eng https://creativecommons.org/licenses/by/3.0/legalcode