Approximation Algorithms for Matroid and Knapsack Means Problems

DOI10.1142/S0217595922400073MaRDI QIDQ6053494zbMATH OpenOpenAlexWikidataFDO

Authors Qian Liu, Yang Zhou, M. Li

Publication date 19 October 2023

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmmatroidknapsackknapsack means problemmatroid means problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Facility Location with Matroid or Knapsack Constraints
• The matroid median problem
• Improved approximation algorithms for matroid and knapsack median problems and applications

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
• Approximation algorithms for the robust facility leasing problem
• Approximation algorithms for two variants of correlation clustering problem
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Least squares quantization in PCM
• Local search algorithms for the red-blue median problem
• Small Space Stream Summary for Matroid Center
• The bi-criteria seeding algorithms for two variants of \(k\)-means problem
• The matroid median problem
• The seeding algorithm for k-means problem with penalties
• The seeding algorithm for spherical \(k\)-means clustering with penalties

Cited in

(2)

• Improved approximation algorithms for matroid and knapsack means problems
• Approximation algorithms for knapsack problems with cardinality constraints

This page was built for publication: 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 Q6053494)