Improved approximation algorithms for matroid and knapsack means problems

DOI10.1142/S012905412246008XMaRDI QIDQ6955223zbMATH OpenFDO

Authors Yang Zhou, Qian Liu

Publication date 23 July 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S012905412246008X

zbMATH Keywords

approximation algorithmknapsack means problemmatroid means problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• A dependent LP-rounding approach for the k-median problem
• A local search approximation algorithm for \(k\)-means clustering
• Adaptive Sampling for k-Means Clustering
• An improved approximation algorithm for knapsack median using sparsification
• Approximation Algorithms for Data Placement Problems
• Approximation Algorithms for Matroid and Knapsack Means Problems
• Fast and Deterministic Approximations for k-Cut.
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Local search algorithms for the red-blue median problem
• Matroid and knapsack center problems
• The matroid median problem

This page was built for publication: Improved approximation algorithms for matroid and knapsack means problems

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