Cover Image

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Banerjee, Sandip, Bartal, Yair, Gottlieb, Lee-Ad, Hovav, Alon
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

FPT Approximations for Fair $k$-Min-Sum-Radii
by: Carta, Lena, et al.
Published: (2024)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

FPT Approximation for Capacitated Sum of Radii
by: Jaiswal, Ragesh, et al.
Published: (2024)

On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering
by: Gadekar, Ameet
Published: (2026)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
by: Bartal, Yair, et al.
Published: (2024)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
by: Nezhad, Sina Bagheri, et al.
Published: (2025)

Approximate Min-Sum Subset Convolution
by: Stoian, Mihail
Published: (2024)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

Min-Sum Set Cover on Parallel Machines
by: Szyfelbein, Michał
Published: (2026)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
by: Bhangale, Amey, et al.
Published: (2026)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

$k$-times bin packing and its application to fair electricity distribution
by: Baghel, Dinesh Kumar, et al.
Published: (2023)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Maintaining $k$-MinHash Signatures over Fully-Dynamic Data Streams with Recovery
by: Clementi, Andrea, et al.
Published: (2024)

Connectivity augmentation is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
by: Dürr, Anita
Published: (2022)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
by: Haeupler, Bernhard, et al.
Published: (2025)

Dynamic k-center clustering with lifetimes
by: Moretti, Simone, et al.
Published: (2026)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
by: Chen, Lin, et al.
Published: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Testing $C_k$-freeness in bounded-arboricity graphs
by: Eden, Talya, et al.
Published: (2024)

Going Beyond Surfaces in Diameter Approximation
by: Włodarczyk, Michał
Published: (2025)

Streaming Diameter of High-Dimensional Points
by: Halldórsson, Magnús M., et al.
Published: (2025)

Diameter Shortcut Sets on Temporal Graphs
by: Quantmeyer, Gerome
Published: (2025)

Diameter Computation on (Random) Geometric Graphs
by: Bläsius, Thomas, et al.
Published: (2026)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
by: Karathanasis, Konstantinos, et al.
Published: (2025)

Max-Min Diversification with Asymmetric Distances
by: Kumpulainen, Iiro, et al.
Published: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)