2026-07-21T23:57:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22134 2024-12-04T06:53:43Z ddc:004 open_access

On the Connected Minimum Sum of Radii Problem An, Hyung-Chan Kao, Mong-Jen connected minimum sum of radii minimum sum of radii connected facility location approximation algorithms Steiner trees In this paper, we consider the study for the connected minimum sum of radii problem. In this problem, we are given as input a metric defined on a set of facilities and clients, along with some cost parameters. The objective is to open a subset of facilities, assign every client to an open facilitiy, and connect open facilities using a Steiner tree so that the weighted (by cost parameters) sum of the maximum assignment distance of each facility and the Steiner tree cost is minimized. This problem introduces the min-sum radii objective, an objective function that is widely considered in the clustering literature, to the connected facility location problem, a well-studied network design/clustering problem. This problem is useful in communication network design on a shared medium, or energy optimization of mobile wireless chargers. We present both a constant-factor approximation algorithm and hardness results for this problem. Our algorithm is based on rounding an LP relaxation that jointly models the min-sum of radii problem and the rooted Steiner tree problem. To round the solution we use a careful clustering procedure that guarantees that every open facility has a proxy client nearby. This allows a reinterpretation for part of the LP solution as a fractional rooted Steiner tree. Combined with a cost filtering technique, this yields a 5.542-approximation algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hyung-Chan An and Mong-Jen Kao 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.7 urn:nbn:de:0030-drops-221342 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode