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

Source abstract

Let $E_1 ,\cdots,E_m$ be subsets of a set V of size n, such that each element of V is in at most k of the $E_i$ and such that each collection of t sets from $E_1 ,\cdots ,E_m$ has a system of distinct representatives (SDR). It is shown that $m/n\leqq (k(k - 1)^r - k)/(2(k - 1)^r - k)$ if $t = 2r - 1$, and $m/n \leqq (k(k - 1)^r - 2)/(2(k - 1)^r - 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.