Improved Approximation Algorithms for Matroid and Knapsack Means Problems

Both matroid means and knapsack means are variations of the classic k-means problem in which we replace the cardinality constraint by matroid constraint or knapsack constraint respectively. In this paper, we give a 64-approximation algorithm for the matroid means problem and a (1128 + ??)-approximation algorithm for the knapsack means problem by using a simpler and more efficient rounding method. We improve previous 304 approximate ratio for the former and 20016 approximate ratio for the latter. In the rounding process, the application of integrality of the intersection of submodular (or matroid) polyhedra provides strong theoretical support. Moreover, we extend this method to matroid means problem with penalties, and give 64 and 880-approximate algorithms for uniform penalties and nonuniform penalties problem.