Rank inequalities and separation algorithms for packing designs and sparse triple systems
✍ Scribed by Lucia Moura
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 220 KB
- Volume
- 297
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
Combinatorial designs ÿnd numerous applications in computer science, and are closely related to problems in coding theory. Packing designs correspond to codes with constant weight; 4-sparse partial Steiner triple systems (4-sparse PSTSs) correspond to erasure-resilient codes that are useful in handling failures in large disk arrays (Chee, Colbourn, Ling, Discrete Appl. Math., to appear; Hellerstein, Gibson, Karp, Katz, Paterson, Algorithmica 12 (1994) 182-208). The study of polytopes associated with combinatorial problems has proven to be important for both algorithms and theory, but only recently the study of design polytopes has been pursued (Moura,