A polyhedral algorithm for packings and designs

DOI10.1007/3-540-48481-7_40MaRDI QIDQ4938787zbMATH OpenFDO

Authors Lucia Moura

Publication date 27 March 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48481-7_40

zbMATH Keywords

\(t\)-designbranch-and-cutcliqueindependent setisomorph rejectionpacking designpacking numberspolyhedral algorithm

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Combinatorial aspects of packing and covering (05B40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

A \(t\)-\((v,k,\lambda)\) packing design (constant weight error-correcting code) is a collection of \(k\)-element sets (called blocks) out of a \(v\)-set such that each \(t\)-subset of the \(v\)-set is contained in at most \(\lambda\) blocks. The packing number, \(D_{\lambda}(v,k,t)\), is the maximum number of blocks in a packing design. A design is simple if it contains no repeated blocks. The author presents a polyhedral algorithm for finding packing numbers. Only simple packing designs are considered. Since \(t\)-designs are packings attaining the first Johnson bound (also called the Schönheim bound), the algorithm can also be used to search for these. When \(\lambda = 1\), the problem of finding a packing number is an instance of the problem of finding the size of a maximum clique (or a maximum independent set) in a graph. When \(\lambda > 1\), we get an instance of a more general problem. These observations are used in the branch-and-cut algorithm presented. The algorithm is sped up by fixing blocks and using partial isomorph rejection. No comparison against other approaches is carried out, but many tables of computational results are presented which will be useful in future comparisons. All test results are for \(\lambda = 1\); it is not clear how well the algorithm performs when \(\lambda > 1\). For the entire collection see [Zbl 0918.00032].

Recommendations

• Rank inequalities and separation algorithms for packing designs and sparse triple systems.
• Constructing designs straightforwardly: Worst arising cases
• Explicit Constructions of Rödl's Asymptotically Good Packings and Coverings
• scientific article; zbMATH DE number 874532
• scientific article; zbMATH DE number 812055

Cited in

(8)

• More-than-nearly-perfect packings and partial designs
• Rank inequalities and separation algorithms for packing designs and sparse triple systems.
• Constructing designs straightforwardly: Worst arising cases
• q-analogs of packing designs
• scientific article; zbMATH DE number 3926962 (Why is no real title available?)
• scientific article; zbMATH DE number 1066165 (Why is no real title available?)
• scientific article; zbMATH DE number 898426 (Why is no real title available?)
• Restricted b‐factors in bipartite graphs and t‐designs

Describes a project that uses

Uses Software

• nauty

This page was built for publication: A polyhedral algorithm for packings and designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938787)