Optimal covering designs: complexity results and new bounds (Q1765237): Difference between revisions

A \(t\)-\((v,m,k,\lambda)\) covering design is a subset \(\mathcal{C}\) of the set of all \(k\)-subsets of a \(v\)-set \(S\), such that, for any \(m\)-subset \(A\) of \(S\), there are at least \(\lambda\) elements of \(\mathcal{C}\) which intersect \(A\) in at least \(t\) elements. The minimum cardinality of a \(t\)-\((v,m,k,1)\) covering design is denoted by \(C(v,m,k,t)\). The authors obtain some new upper bounds for \(C(v,m,k,t)\) for certain parameter values. They also consider the following variation of the problem. Given a subset \(\mathcal{T}\) of the set of all \(k\)-subsets of a \(v\)-set \(S\), find a minimum cardinality subset \(\mathcal{C}\) of \(\mathcal{T}\) such that, for any set \(A\) in \(\mathcal{T}\), there exists at least one set in \(\mathcal{C}\) which intersects \(A\) in at least \(t\) elements. The authors prove that the computational complexity of this problem is \(\log{| \mathcal{T}}| \)-approximable and that it can not be approximated within a factor smaller than \(\log{| \mathcal{T}| }\), unless P = NP.