A unified framework of FPT approximation algorithms for clustering problems
From MaRDI portal
Publication:6065394
DOI10.4230/lipics.isaac.2020.5OpenAlexW3113496837MaRDI QIDQ6065394
Qilong Feng, Jinhui Xu, Zhen Zhang, Ziyun Huang, Jianxin Wang
Publication date: 14 November 2023
Full work available at URL: https://doi.org/10.4230/lipics.isaac.2020.5
Related Items (5)
Better guarantees for \(k\)-median with service installation costs ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Lossy kernelization of same-size clustering ⋮ Lossy kernelization of same-size clustering ⋮ On parameterized approximation algorithms for balanced clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
- A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
- Faster algorithms for the constrained \(k\)-means problem
- A constant-factor approximation algorithm for the \(k\)-median problem
- A constant factor approximation for lower-bounded \(k\)-median
- Improved PTAS for the constrained \(k\)-means problem
- Approximating $k$-Median via Pseudo-Approximation
- Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
- All-Norms and All-L_p-Norms Approximation Algorithms
- Approximation Algorithms for Data Placement Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- Linear-time approximation schemes for clustering problems in any dimensions
- Greedy Strikes Back: Improved Facility Location Algorithms
- Local Search Heuristics for k-Median and Facility Location Problems
- A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- Constant-Factor FPT Approximation for Capacitated k-Median
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
- Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
- A Unified Framework for Clustering Constrained Data without Locality Property
- The Priority k-Median Problem
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: A unified framework of FPT approximation algorithms for clustering problems
