On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems

Let E₁ ,⋯,Eₘ be subsets of a set V of size n, such that each element of V is in at most k of the Eᵢ and such that each collection of t sets from E₁ ,⋯ ,Eₘ has a system of distinct representatives (SDR). It is shown that m/n (k(k - 1)ʳ - k)/(2(k - 1)ʳ - k) if $t = 2r - 1$, and m/n (k(k - 1)ʳ - 2)/(2(k - 1)ʳ - 2) if $t = 2r$. Moreover it is shown that these upper bounds are the best possible. From these results the “worst-case ratio” of certain heuristics for the problem of finding a maximum collection of pairwise disjoint sets among a given collection of sets of size k is derived.