Parameterized approximation schemes for fair-range clustering

DOI10.1016/J.IC.2026.105457MaRDI QIDQ7286060zbMATH OpenFDO

Authors Zhen Zhang, Xiaohong Chen, Limei Liu, Jie Chen, Junyu Huang, Qilong Feng

Publication date 23 June 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105457

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• A unified framework for clustering constrained data without locality property
• Approximation algorithms for fair k-median problem without fairness violation
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Bounded geometries, fractals, and low-distortion embeddings
• Breaching the 2 LMP approximation barrier for facility location with applications to \(k\)-median
• Budgeted red-blue median and its generalizations
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Extensions of Lipschitz mappings into a Hilbert space
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Faster algorithms for the constrained k-means problem
• FPT approximation for capacitated sum of radii
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
• Improved bi-point rounding algorithms and a golden barrier for \(k\)-median
• Linear-time approximation schemes for clustering problems in any dimensions
• Local search algorithms for the red-blue median problem
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• On the fixed-parameter tractability of capacitated clustering
• Optimal terminal dimensionality reduction in Euclidean space
• Parameterized approximation for robust clustering in discrete geometric spaces
• Proportionally fair clustering revisited
• The matroid median problem
• Tight analysis of a multiple-swap heuristic for budgeted red-blue median
• Tight FPT approximation for socially fair clustering
• Towards a theoretical understanding of why local search works for clustering with fair-center representation

This page was built for publication: Parameterized approximation schemes for fair-range clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7286060)