Approximation Algorithms for Matroid and Knapsack Means Problems

Ao Zhao (), Qian Liu (), Yang Zhou () and Min Li
Additional contact information
Ao Zhao: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China
Qian Liu: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China
Yang Zhou: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China
Min Li: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 01, 1-16

Abstract: In this paper, we concentrate on studying the k-means problem with a matroid or a knapsack constraint. In the matroid means problem, given an observation set and a matroid, the goal is to find a center set from the independent sets to minimize the cost. By using the linear programming (LP)-rounding technology, we obtain a constant approximation guarantee. For the knapsack means problem, we adopt a similar strategy to that of matroid means problem, whereas the difference is that we add a knapsack covering inequality to the relaxed LP in order to decrease the unbounded integrality gap.

Keywords: Approximation algorithm; matroid means problem; knapsack means problem; matroid; knapsack (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400073
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:01:n:s0217595922400073

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400073

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().