A fast approximation algorithm for the multicovering problem (Q1082267): Difference between revisions

The multicovering problem requires to find the (linear) least total cost for a group of sets with the assumption that given elements are covered at least given times by elements of the group. This problem is NP- complete. The paper gives an algorithm which uses O(max\(\{\) n,m\(\}\cdot n)\) time, where n is the number of prescribed sets, and m is the number of elements to be covered. The coding of the algorithm is very easy. The paper contains a sharp bound for the ratio of achieved and optimal cost, the example can be easily received from an increasing group of sets. One can ask for the probability distribution of the ratio. This is interesting because of the fact that the bound for the ratio is painfully large.