Cover Image

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nezhad, Sina Bagheri, Bandyapadhyay, Sayan, Chen, Tianzhi
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 Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

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

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

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

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

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

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

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

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

Extraction Theorems With Small Extraction Numbers
by: Agarwal, Arjun, et al.
Published: (2024)

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

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

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
by: Banerjee, Sandip, et al.
Published: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
by: Haeupler, Bernhard, et al.
Published: (2026)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

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

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

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

Approximation Algorithms for Fair Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2025)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
by: Suzuki, Ryo, et al.
Published: (2026)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
by: Rui, Xiaobin, et al.
Published: (2025)

Fair Center Clustering in Sliding Windows
by: Ceccarello, Matteo, et al.
Published: (2025)

Fair Clustering in the Sliding Window Model
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
by: Maity, Binita, et al.
Published: (2024)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
by: Braverman, Vladimir, et al.
Published: (2025)

Fair Correlation Clustering Meets Graph Parameters
by: Blaha, Johannes, et al.
Published: (2026)