Approximating Minimum Spanning Sets in Hypergraphs and Polymatroids

Abstract

We present a new analysis of the greedy algorithm for the problem of finding a minimum spanning subset in k-polymatroids. This algorithm has a performance ratio of approximately, which is best possible for large. A consequence of this algorithm is a polynomial time approximation algorithm with approximation ratio for finding minimum weight spanning subhypergraphs in (k + 1)-restricted hypergraphs. This generalization of the well-known set cover problem naturally arises when computing Steiner minimum trees. Other applications of the algorithm include the rigidity problem in statics.