Clustering under a knapsack constraint: parameterized approximation for the knapsack median problem

DOI10.1016/J.TCS.2025.115426MaRDI QIDQ6930251zbMATH OpenFDO

Authors Zhen Zhang, Zhuohang Gao, Limei Liu, Yao Liu, Jie Chen, Qilong Feng

Publication date 16 September 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115426

zbMATH Keywords

approximation algorithmsfixed-parameter tractabilityknapsack median

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Discrete location and assignment (90B80) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• scientific article; zbMATH DE number 7651201 (Why is no real title available?)
• An improved approximation algorithm for knapsack median using sparsification
• Approximation algorithms for the lower-bounded knapsack median problem
• Breaching the 2 LMP approximation barrier for facility location with applications to \(k\)-median
• Clustering what matters: optimal approximation for clustering with outliers
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Constant factor approximation algorithm for the knapsack median problem
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• FPT approximation for capacitated clustering with outliers
• FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Combinatorial Algorithms for Facility Location Problems
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Improved bi-point rounding algorithms and a golden barrier for \(k\)-median
• Nonlinear dimension reduction via outer bi-Lipschitz extensions
• 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 parameterized approximation algorithms for balanced clustering
• On the fixed-parameter tractability of capacitated clustering
• Parameterized approximation for robust clustering in discrete geometric spaces
• The matroid median problem
• k-median/means with outliers revisited: a simple fpt approximation

This page was built for publication: Clustering under a knapsack constraint: parameterized approximation for the knapsack median problem

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