FPT Approximation for Constrained Metric k-Median/Means

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

zbMATH Keywords

approximation algorithms\(k\)-means\(k\)-medianparameterised algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

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

This page was built for publication: FPT Approximation for Constrained Metric k-Median/Means