Optimal covering designs: complexity results and new bounds
type: Item
instance of: scholarly article
title: Optimal covering designs: complexity results and new bounds
zbMATH Open document ID: 1063.05031
author: Federico Montecalvo
author: Gianluca Rossi
author: Pilu Crescenzi
published in: Discrete Applied Mathematics
publication date: 2005-02-23T00:00:00Z
review text: 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.
reviewed by: Luc Teirlinck
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 05-02
zbMATH DE Number: 2137272
zbMATH Keywords: optimal lottery scheme
MaRDI profile type: Publication
full work available at URL: j.dam.2003.11.006
OpenAlex ID: W2044660400
cites work: Q4258216
cites work: Q3936754
cites work: On the covering of \(t\)-sets with \((t+1)\)-sets: \(C(9,5,4)\) and \(C(10,6,5)\)
cites work: Large sets of coverings
cites work: New constructions for covering designs
cites work: Approximation algorithms for combinatorial problems
cites work: On large sets of disjoint Steiner triple systems. VI
cites work: Q4026151
cites work: Q4304396
cites work: Q3221403
cites work: Q4527015
cites work: A completion of Lu's determination of the spectrum for large sets of disjoint Steiner triple systems
DOI: 10.1016/J.DAM.2003.11.006
Recommended article: Asymptotically optimal covering designs
Recommended article: On the optimality of a class of minimal covering designs
Recommended article: New upper bounds on the minimum size of covering designs
Recommended article: Asymptotic Bounds for General Covering Designs
Recommended article: General upper bounds on the minimum size of covering designs
Recommended article: Bounds for optimal coverings
Recommended article: Efficient covering designs of the complete graph
description: scientific article; zbMATH DE number 2137272