On the Parameterized Complexity of Min-Sum-Radii

Haiko M\"uller; Melanie Schmidt; Pankaj Kumar; Sebastian Ordyniak

arxiv: 2605.22804 · v1 · pith:GTWNDTMUnew · submitted 2026-05-21 · 💻 cs.DS · cs.CC

On the Parameterized Complexity of Min-Sum-Radii

Pankaj Kumar , Haiko M\"uller , Sebastian Ordyniak , Melanie Schmidt This is my paper

Pith reviewed 2026-05-22 03:00 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords Min-Sum-Radiiparameterized complexityW[1]-hardnessfixed-parameter tractabilitytreewidthgraph metricsclusteringbipartite graphs

0 comments

The pith

Min-Sum-Radii clustering is W[1]-hard parameterized by number of clusters plus total cost on weighted bipartite graph metrics, yet fixed-parameter tractable when treewidth is added to the cost parameter.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that finding a small number of clusters to minimize the sum of their radii remains computationally hard on distances taken from weighted graphs, even when the graphs are bipartite and both the number of clusters and the total sum of radii are treated as small parameters. It strengthens this by proving hardness also when parameterized by vertex cover number plus clusters, and even on complete graphs or cliques. On the positive side, the same cost parameter combines with treewidth to yield an FPT algorithm that improves on a prior XP result. A sympathetic reader would care because these results draw a precise map of when exact solutions for this clustering task are feasible on network-like data versus when they are unlikely to exist.

Core claim

On metrics induced by undirected weighted graphs, the Min-Sum-Radii problem is W[1]-hard parameterized by k plus Delta even when restricted to bipartite graphs; it remains W[1]-hard parameterized by vertex cover number plus k and when restricted to cliques or complete bipartite graphs; yet the problem is FPT when parameterized by treewidth plus Delta, via an existing XP algorithm for treewidth.

What carries the argument

The shortest-path metric of an undirected weighted graph, used both to construct hardness reductions that preserve small k and Delta and to enable dynamic programming over tree decompositions when treewidth is bounded.

If this is right

No FPT algorithm for MSR exists under standard assumptions when k and the sum of radii are both small, even on bipartite networks.
The same hardness holds on dense graphs such as cliques when using the combined k and Delta parameter.
Exact solutions become feasible in FPT time once the input graph has bounded treewidth together with bounded total radius cost.
Prior XP algorithms parameterized solely by treewidth cannot be improved to FPT without incorporating the cost parameter.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Network clustering tasks may become practically solvable by first computing a tree decomposition and then applying the FPT routine when total radius cost is modest.
Similar hardness boundaries could be explored for other radius-based or sum-based clustering objectives on the same graph metrics.
Approximation schemes might still exist for the hard parameter regimes even if exact FPT algorithms do not.

Load-bearing premise

All distances supplied to the algorithm must be exactly the shortest-path distances of some undirected graph rather than arbitrary numbers satisfying the triangle inequality.

What would settle it

An algorithm that solves MSR in f(k, Delta) * n^c time on weighted bipartite graphs for some computable f and constant c would falsify the W[1]-hardness claim; conversely, an instance family on low-treewidth graphs where the combined parameter treewidth plus Delta yields no fpt runtime would falsify the tractability claim.

read the original abstract

In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these points such that every point of X is assigned to one of the clusters, minimizing the sum of the radii of the clusters. The problem is known to be NP-hard even on metrics induced by weighted planar graphs and metrics with constant doubling dimension, as shown by Gibson et al. (SWAT 2008). In this work, we investigate the parameterized complexity of MSR on metrics induced by undirected graphs. We distinguish between weighted graph metrics (with positive edge weights) and unweighted graph metrics (where all edges have unit weight). Weighted Graph Metrics: We show that MSR is W[1]-hard on metrics induced by weighted bipartite graphs, when parameterized by the combined parameter k (the number of clusters) and Delta (the cost of the clustering). We then investigate the structural parameterized complexity of the problem. Drexler et al. (arXiv:2310.02130) showed that the MSR problem admits an XP algorithm on metrics induced by weighted graphs when parameterized by treewidth, and asked whether this can be improved to fixed-parameter tractability. We first answer their question in the negative, and more strongly show that MSR stays W[1]-hard on metrics induced by undirected weighted bipartite graphs when parameterized by the vertex cover number plus k. We then turn our attention to parameters for dense graphs and show that MSR remains W[1]-hard when parameterized by k+Delta even on cliques and complete bipartite graphs. On the positive side, we employ the known XP algorithm parameterized by treewidth, to show that the MSR problem is FPT when parameterized by the parameter treewidth plus Delta.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper adds several new W[1]-hardness results for Min-Sum-Radii under k+Delta and vertex-cover-plus-k, while claiming an FPT algorithm for treewidth plus Delta that directly answers an open question.

read the letter

The main things to know are the new hardness results and the resolution of the Drexler et al. open question on treewidth parameterization. They prove W[1]-hardness for the combined parameter k plus Delta on weighted bipartite graph metrics, and strengthen this to hardness for vertex cover number plus k. They also show hardness for k plus Delta even on cliques and complete bipartite graphs. On the positive side they claim an FPT result for treewidth plus Delta by building on the existing XP algorithm for treewidth alone.

Referee Report

1 major / 0 minor

Summary. The paper studies the parameterized complexity of Min-Sum-Radii (MSR) clustering on shortest-path metrics of undirected graphs. It establishes W[1]-hardness for the combined parameter k + Delta on weighted bipartite graphs, W[1]-hardness for vertex cover number + k on weighted graphs, and W[1]-hardness for k + Delta even on cliques and complete bipartite graphs. On the positive side, it claims an FPT algorithm for the combined parameter treewidth + Delta by invoking a known XP algorithm parameterized solely by treewidth.

Significance. The hardness results strengthen existing NP-hardness statements by providing parameterized lower bounds under natural structural parameters. If the FPT claim for treewidth + Delta holds, it would resolve the open question from Drexler et al. in the affirmative for this combined parameter. The manuscript correctly distinguishes weighted and unweighted cases and uses standard tools (reductions and treewidth DP).

major comments (1)

Abstract and positive-results section: the claim that the known XP algorithm parameterized by treewidth yields FPT for the combined parameter treewidth + Delta is not justified. An XP runtime of the form n^{f(tw)} becomes n^{f(p)} for p = tw + Delta (since tw ≤ p), which is XP but not FPT. Establishing FPT requires an additional, explicit argument—such as a kernel whose size is bounded by a function of tw and Delta, or a DP on the tree decomposition whose state space is bounded by f(tw, Delta) by exploiting that the objective value equals Delta. This is load-bearing for the main positive result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for their thorough review and constructive criticism. We address the major comment below.

read point-by-point responses

Referee: Abstract and positive-results section: the claim that the known XP algorithm parameterized by treewidth yields FPT for the combined parameter treewidth + Delta is not justified. An XP runtime of the form n^{f(tw)} becomes n^{f(p)} for p = tw + Delta (since tw ≤ p), which is XP but not FPT. Establishing FPT requires an additional, explicit argument—such as a kernel whose size is bounded by a function of tw and Delta, or a DP on the tree decomposition whose state space is bounded by f(tw, Delta) by exploiting that the objective value equals Delta. This is load-bearing for the main positive result.

Authors: We thank the referee for highlighting this important point. We acknowledge that the current manuscript does not provide the necessary additional argument to establish fixed-parameter tractability for the combined parameter treewidth + Delta using the known XP algorithm for treewidth. The runtime remains in XP rather than FPT without further work. We will revise the manuscript to address this. In the revised version, we will either include a detailed explanation of how the dynamic programming can be adapted to run in time f(tw, Delta) * poly(n) by bounding the possible radius assignments using the objective value Delta, or we will retract the FPT claim and discuss the open status of this question. This revision will be made to both the abstract and the relevant sections of the paper. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper's hardness results are obtained via explicit reductions from known W[1]-hard problems on graph metrics, and the positive FPT result for treewidth plus Delta invokes an external XP algorithm from Drexler et al. (arXiv:2310.02130) without any self-citation that encodes the target statement or any fitted parameter renamed as a prediction. All steps remain independent of the paper's own outputs by construction, satisfying the criteria for a self-contained derivation against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard parameterized complexity assumptions (FPT ≠ W[1]) and on the definition of graph metrics; no free parameters are fitted and no new entities are postulated.

axioms (2)

domain assumption FPT ≠ W[1]
Invoked implicitly by every W[1]-hardness statement to conclude that no f(k,Delta) n^O(1) algorithm exists.
domain assumption Distances are shortest-path distances in an undirected graph
Stated in the problem definition and used in all reductions and the treewidth DP.

pith-pipeline@v0.9.0 · 5874 in / 1413 out tokens · 28605 ms · 2026-05-22T03:00:08.854740+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

1007/s00453-001-0110-y,doi:10.1007/S00453-001-0110-Y

URL: https://doi.org/10. 1007/s00453-001-0110-y,doi:10.1007/S00453-001-0110-Y. 2 Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems.SIAM J. Comput., 33(3):544–562, 2004.doi:10.1137/S0097539702416402. 3 Sayan Bandyapadhyay, William Lochet, and Sa...

work page doi:10.1007/s00453-001-0110-y 2004
[2]

4 Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav

URL:https://doi.org/10.4230/ LIPIcs.SoCG.2023.12,doi:10.4230/LIPICS.SOCG.2023.12. 4 Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Improved fixed-parameter bounds for min-sum-radii and diameters k-clustering and their fair variants. In Toby Walsh, Julie Shah, and Zico Kolter, editors,AAAI-25, Sponsored by the Association for the Ad- vancem...

work page doi:10.4230/lipics.socg.2023.12 2023
[3]

5 Babak Behsaz and Mohammad R

URL:https://doi.org/10.1609/aaai.v39i15.33699, doi:10.1609/AAAI.V39I15.33699. 5 Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. In Fedor V. Fomin and Petteri Kaski, editors,Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6,

work page doi:10.1609/aaai.v39i15.33699 2012
[4]

6 Babak Behsaz and Mohammad R

doi: 10.1007/978-3-642-31155-0\_7. 6 Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and dia- meters clustering.Algorithmica, 73(1):143–165,

work page doi:10.1007/978-3-642-31155-0
[5]

7 Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos

URL: https://doi.org/10.1007/ s00453-014-9907-3,doi:10.1007/S00453-014-9907-3. 7 Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geo- metric clustering to minimize the sum of cluster sizes. In Gerth Stølting Brodal and Stefano Leonardi, editors,Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca,...

work page doi:10.1007/s00453-014-9907-3 2005
[6]

11 Moses Charikar and Rina Panigrahy

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2024.16,doi:10.4230/LIPICS.ISAAC.2024.16. 11 Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors,Proceedings on 33rd 22 On the Parameterized Complexity of Min-Sum-Radii Annual ACM Symposium on Theory of C...

work page doi:10.4230/lipics.isaac.2024.16 2024
[7]

13 Marek Cygan, Fedor V

URL: https://doi.org/10.1609/aaai.v38i18.30053,doi:10.1609/AAAI.V38I18.30053. 13 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

work page doi:10.1609/aaai.v38i18.30053
[8]

6 Josep Díaz, Olli Pottonen, Maria J

doi:10.1007/978-3-319-21275-3. 14 Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer,

work page doi:10.1007/978-3-319-21275-3
[9]

Downey and Michael R

15 Rodney G. Downey and Michael R. Fellows. Fixed-parameter intractability. InProceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992, pages 36–49. IEEE Computer Society, 1992.doi:10.1109/SCT.1992.215379. 16 Lukas Drexler, Jan Höckendorff, Joshua Könen, and Kevin Schewior. Clustering graphs...

work page doi:10.1109/sct.1992.215379 1992
[10]

48550/ARXIV.2310.02130

URL: https://doi.org/10.48550/arXiv.2310.02130, arXiv:2310.02130, doi:10. 48550/ARXIV.2310.02130. 17 Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems.Theor. Comput. Sci., 410(1):53–61,

work page doi:10.48550/arxiv.2310.02130
[11]

TCS.2008.09.065

URL:https://doi.org/10.1016/j.tcs.2008.09.065, doi:10.1016/J. TCS.2008.09.065. 18 Arnold Filtser and Ameet Gadekar. FPT approximations for capacitated sum of radii and diameters.CoRR, abs/2409.04984,

work page doi:10.1016/j.tcs.2008.09.065 2008
[12]

04984,arXiv:2409.04984,doi:10.48550/ARXIV.2409.04984

URL: https://doi.org/10.48550/arXiv.2409. 04984,arXiv:2409.04984,doi:10.48550/ARXIV.2409.04984. 19 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh. Exact exponential algorithms for clustering problems. In Holger Dell and Jesper Nederlof, editors,17th International Symposium on Parameterized and Exact Computation, IPEC 20...

work page doi:10.48550/arxiv.2409 2022
[13]

20 Fedor V

URL:https://doi.org/10.4230/LIPIcs.IPEC.2022.13, doi: 10.4230/LIPICS.IPEC.2022.13. 20 Fedor V. Fomin and Dieter Kratsch.Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.doi:10.1007/978-3-642-16533-7. 21 Zachary Friggstad and Mahya Jamshidian. Improved polynomial-time approximations for clustering with mi...

work page doi:10.4230/lipics.ipec.2022.13 2022
[14]

org/10.4230/LIPIcs.ESA.2022.56,doi:10.4230/LIPICS.ESA.2022.56

URL:https://doi. org/10.4230/LIPIcs.ESA.2022.56,doi:10.4230/LIPICS.ESA.2022.56. 22 Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On metric clustering to minimize the sum of radii. In Joachim Gudmundsson, editor,Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4...

work page doi:10.4230/lipics.esa.2022.56 2022
[15]

24 Teofilo F

doi: 10.1137/100798144. 24 Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance.Theor. Comput. Sci., 38:293–306, 1985.doi:10.1016/0304-3975(85)90224-5. P. Kumar, H. Müller, S. Ordyniak, and M. Schmidt 23 25 Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems.Discret. Appl. Math., 1(3):209–215, 1979.doi...

work page doi:10.1137/100798144 1985
[16]

On the compl exity of k-sat

URL:https://doi.org/10.1006/jcss.2000.1727, doi:10.1006/ JCSS.2000.1727. 27 Tanmay Inamdar and Kasturi R. Varadarajan. Capacitated sum-of-radii clustering: An FPT approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors,28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), vo...

work page doi:10.1006/jcss.2000.1727 2000
[17]

28 Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

URL:https://doi.org/10.4230/LIPIcs.ESA.2020.62, doi: 10.4230/LIPICS.ESA.2020.62. 28 Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT approximation for capacitated sum of radii. In Venkatesan Guruswami, editor,15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 ofLIPIcs, page...

work page doi:10.4230/lipics.esa.2020.62 2020
[18]

29 Nissan Lev-Tov and David Peleg

URL: https://doi.org/10.4230/LIPIcs.ITCS.2024.65,doi:10.4230/LIPICS.ITCS.2024.65. 29 Nissan Lev-Tov and David Peleg. Polynomial time approximation schemes for base station coverage with minimum total radii.Comput. Networks, 47(4):489–501,

work page doi:10.4230/lipics.itcs.2024.65 2024
[19]

30 Dániel Marx

URL:https: //doi.org/10.1016/j.comnet.2004.08.012,doi:10.1016/J.COMNET.2004.08.012. 30 Dániel Marx. On the optimality of planar and geometric approximation schemes. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 338–348. IEEE,

work page doi:10.1016/j.comnet.2004.08.012 2004
[20]

22 Peter J Slater

32 Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.J. Comput. Syst. Sci., 67(4):757– 771, 2003.doi:10.1016/S0022-0000(03)00078-3. 33Guido Proietti and Peter Widmayer. Partitioning the nodes of a graph to minimize the sum of subgraph radii. In Tetsuo Asano, edit...

work page doi:10.1016/s0022-0000(03)00078-3 2003

[1] [1]

1007/s00453-001-0110-y,doi:10.1007/S00453-001-0110-Y

URL: https://doi.org/10. 1007/s00453-001-0110-y,doi:10.1007/S00453-001-0110-Y. 2 Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems.SIAM J. Comput., 33(3):544–562, 2004.doi:10.1137/S0097539702416402. 3 Sayan Bandyapadhyay, William Lochet, and Sa...

work page doi:10.1007/s00453-001-0110-y 2004

[2] [2]

4 Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav

URL:https://doi.org/10.4230/ LIPIcs.SoCG.2023.12,doi:10.4230/LIPICS.SOCG.2023.12. 4 Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Improved fixed-parameter bounds for min-sum-radii and diameters k-clustering and their fair variants. In Toby Walsh, Julie Shah, and Zico Kolter, editors,AAAI-25, Sponsored by the Association for the Ad- vancem...

work page doi:10.4230/lipics.socg.2023.12 2023

[3] [3]

5 Babak Behsaz and Mohammad R

URL:https://doi.org/10.1609/aaai.v39i15.33699, doi:10.1609/AAAI.V39I15.33699. 5 Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. In Fedor V. Fomin and Petteri Kaski, editors,Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6,

work page doi:10.1609/aaai.v39i15.33699 2012

[4] [4]

6 Babak Behsaz and Mohammad R

doi: 10.1007/978-3-642-31155-0\_7. 6 Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and dia- meters clustering.Algorithmica, 73(1):143–165,

work page doi:10.1007/978-3-642-31155-0

[5] [5]

7 Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos

URL: https://doi.org/10.1007/ s00453-014-9907-3,doi:10.1007/S00453-014-9907-3. 7 Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geo- metric clustering to minimize the sum of cluster sizes. In Gerth Stølting Brodal and Stefano Leonardi, editors,Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca,...

work page doi:10.1007/s00453-014-9907-3 2005

[6] [6]

11 Moses Charikar and Rina Panigrahy

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2024.16,doi:10.4230/LIPICS.ISAAC.2024.16. 11 Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors,Proceedings on 33rd 22 On the Parameterized Complexity of Min-Sum-Radii Annual ACM Symposium on Theory of C...

work page doi:10.4230/lipics.isaac.2024.16 2024

[7] [7]

13 Marek Cygan, Fedor V

URL: https://doi.org/10.1609/aaai.v38i18.30053,doi:10.1609/AAAI.V38I18.30053. 13 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

work page doi:10.1609/aaai.v38i18.30053

[8] [8]

6 Josep Díaz, Olli Pottonen, Maria J

doi:10.1007/978-3-319-21275-3. 14 Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer,

work page doi:10.1007/978-3-319-21275-3

[9] [9]

Downey and Michael R

15 Rodney G. Downey and Michael R. Fellows. Fixed-parameter intractability. InProceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992, pages 36–49. IEEE Computer Society, 1992.doi:10.1109/SCT.1992.215379. 16 Lukas Drexler, Jan Höckendorff, Joshua Könen, and Kevin Schewior. Clustering graphs...

work page doi:10.1109/sct.1992.215379 1992

[10] [10]

48550/ARXIV.2310.02130

URL: https://doi.org/10.48550/arXiv.2310.02130, arXiv:2310.02130, doi:10. 48550/ARXIV.2310.02130. 17 Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems.Theor. Comput. Sci., 410(1):53–61,

work page doi:10.48550/arxiv.2310.02130

[11] [11]

TCS.2008.09.065

URL:https://doi.org/10.1016/j.tcs.2008.09.065, doi:10.1016/J. TCS.2008.09.065. 18 Arnold Filtser and Ameet Gadekar. FPT approximations for capacitated sum of radii and diameters.CoRR, abs/2409.04984,

work page doi:10.1016/j.tcs.2008.09.065 2008

[12] [12]

04984,arXiv:2409.04984,doi:10.48550/ARXIV.2409.04984

URL: https://doi.org/10.48550/arXiv.2409. 04984,arXiv:2409.04984,doi:10.48550/ARXIV.2409.04984. 19 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh. Exact exponential algorithms for clustering problems. In Holger Dell and Jesper Nederlof, editors,17th International Symposium on Parameterized and Exact Computation, IPEC 20...

work page doi:10.48550/arxiv.2409 2022

[13] [13]

20 Fedor V

URL:https://doi.org/10.4230/LIPIcs.IPEC.2022.13, doi: 10.4230/LIPICS.IPEC.2022.13. 20 Fedor V. Fomin and Dieter Kratsch.Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.doi:10.1007/978-3-642-16533-7. 21 Zachary Friggstad and Mahya Jamshidian. Improved polynomial-time approximations for clustering with mi...

work page doi:10.4230/lipics.ipec.2022.13 2022

[14] [14]

org/10.4230/LIPIcs.ESA.2022.56,doi:10.4230/LIPICS.ESA.2022.56

URL:https://doi. org/10.4230/LIPIcs.ESA.2022.56,doi:10.4230/LIPICS.ESA.2022.56. 22 Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On metric clustering to minimize the sum of radii. In Joachim Gudmundsson, editor,Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4...

work page doi:10.4230/lipics.esa.2022.56 2022

[15] [15]

24 Teofilo F

doi: 10.1137/100798144. 24 Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance.Theor. Comput. Sci., 38:293–306, 1985.doi:10.1016/0304-3975(85)90224-5. P. Kumar, H. Müller, S. Ordyniak, and M. Schmidt 23 25 Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems.Discret. Appl. Math., 1(3):209–215, 1979.doi...

work page doi:10.1137/100798144 1985

[16] [16]

On the compl exity of k-sat

URL:https://doi.org/10.1006/jcss.2000.1727, doi:10.1006/ JCSS.2000.1727. 27 Tanmay Inamdar and Kasturi R. Varadarajan. Capacitated sum-of-radii clustering: An FPT approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors,28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), vo...

work page doi:10.1006/jcss.2000.1727 2000

[17] [17]

28 Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

URL:https://doi.org/10.4230/LIPIcs.ESA.2020.62, doi: 10.4230/LIPICS.ESA.2020.62. 28 Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT approximation for capacitated sum of radii. In Venkatesan Guruswami, editor,15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 ofLIPIcs, page...

work page doi:10.4230/lipics.esa.2020.62 2020

[18] [18]

29 Nissan Lev-Tov and David Peleg

URL: https://doi.org/10.4230/LIPIcs.ITCS.2024.65,doi:10.4230/LIPICS.ITCS.2024.65. 29 Nissan Lev-Tov and David Peleg. Polynomial time approximation schemes for base station coverage with minimum total radii.Comput. Networks, 47(4):489–501,

work page doi:10.4230/lipics.itcs.2024.65 2024

[19] [19]

30 Dániel Marx

URL:https: //doi.org/10.1016/j.comnet.2004.08.012,doi:10.1016/J.COMNET.2004.08.012. 30 Dániel Marx. On the optimality of planar and geometric approximation schemes. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 338–348. IEEE,

work page doi:10.1016/j.comnet.2004.08.012 2004

[20] [20]

22 Peter J Slater

32 Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.J. Comput. Syst. Sci., 67(4):757– 771, 2003.doi:10.1016/S0022-0000(03)00078-3. 33Guido Proietti and Peter Widmayer. Partitioning the nodes of a graph to minimize the sum of subgraph radii. In Tetsuo Asano, edit...

work page doi:10.1016/s0022-0000(03)00078-3 2003