A PTAS framework for clustering problems in doubling metrics

DOI10.1007/978-3-031-49190-0_28MaRDI QIDQ6591490zbMATH OpenFDO

Authors Di Wu, Jinhui Xu, Jianxin Wang

Publication date 22 August 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49190-0_28

zbMATH Keywords

\(k\)-medianapproximation algorithm

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A birthday repetition theorem and complexity of approximating dense CSPs
• A constant factor approximation algorithm for fault-tolerant k-median
• A constant factor approximation for lower-bounded \(k\)-median
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A local search approximation algorithm for the uniform capacitated k-facility location problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median 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
• A unified framework of FPT approximation algorithms for clustering problems
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• Approximation Schemes for Capacitated Clustering in Doubling Metrics
• Better guarantees for \(k\)-median with service installation costs
• Breaching the 2 LMP approximation barrier for facility location with applications to \(k\)-median
• Bypassing the embedding
• Constant-Factor FPT Approximation for Capacitated k-Median
• Facility location with service installation costs
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 1803756 (Why is no real title available?)
• scientific article; zbMATH DE number 4123493 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
• Improved PTAS for the constrained \(k\)-means problem
• Near-linear Time Approximation Schemes for Clustering in Doubling Metrics
• On the cost of essentially fair clusterings
• Primal-dual algorithms for connected facility location problems
• The Priority k-Median Problem

This page was built for publication: A PTAS framework for clustering problems in doubling metrics

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