FPT Approximation for Constrained Metric k-Median/Means
From MaRDI portal
Publication:6089659
DOI10.4230/lipics.ipec.2020.14arXiv2007.11773OpenAlexW3118018398MaRDI QIDQ6089659
Dishant Goyal, Amit Kumar, Ragesh Jaiswal
Publication date: 13 November 2023
Full work available at URL: https://arxiv.org/abs/2007.11773
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Tight FPT approximation for socially fair clustering ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The planar \(k\)-means problem is NP-hard
- A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
- NP-hardness of Euclidean sum-of-squares clustering
- A clustering algorithm based on graph connectivity
- Faster algorithms for the constrained \(k\)-means problem
- A constant-factor approximation algorithm for the \(k\)-median problem
- Faster balanced clusterings in high dimension
- Achieving anonymity via clustering
- All-Norms and All-L_p-Norms Approximation Algorithms
- 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
- A new greedy approach for facility location problems
- A PTAS for k-means clustering based on weak coresets
- Random sampling with a reservoir
- Greedy Strikes Back: Improved Facility Location Algorithms
- A local search approximation algorithm for k-means clustering
- Approximating capacitated k-median with (1 + ∊)k open facilities
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- Local Search Heuristics for k-Median and Facility Location Problems
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
- A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- Proportional Approval Voting, Harmonic k-median, and Negative Association
- Constant-Factor FPT Approximation for Capacitated k-Median
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
- Constant approximation for k-median and k-means with outliers via iterative rounding
- A Unified Framework for Clustering Constrained Data without Locality Property
- k-means requires exponentially many iterations even in the plane
- Approximating k-median via pseudo-approximation
