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

C.A.J. Hurkens, A. Schrijver

Research output: Contribution to journalArticleAcademicpeer-review

481 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)68-72
JournalSIAM Journal on Discrete Mathematics
Volume2
Issue number1
DOIs
Publication statusPublished - 1989

Fingerprint

Dive into the research topics of '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'. Together they form a unique fingerprint.

Cite this