Treffer: Rank inequalities and separation algorithms for packing designs and sparse triple systems

Title:
Rank inequalities and separation algorithms for packing designs and sparse triple systems
Authors:
MOURA, Lucia
Source:
Latin American Theoretical InformaticsTheoretical computer science. 297(1-3):367-384
Publisher Information:
Amsterdam: Elsevier, 2003.
Publication Year:
2003
Physical Description:
print, 25 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Plans d'expériences et configurations, Designs and configurations, Algèbre, Algebra, Théorie des nombres, Number theory, Analyse mathématique, Mathematical analysis, Calcul des variations et contrôle optimal, Calculus of variations and optimal control, Géométrie, Geometry, Géométrie convexe et discrète, Convex and discrete geometry, Algorithme, Algorithm, Algoritmo, Application, Aplicación, Article, Artículo, Borne supérieure, Upper bound, Cota superior, Codage, Coding, Codificación, Code, Código, Conception ordinateur, Computer design, Concepción ordenador, Conception système, System design, Concepción sistema, Conception, Design, Diseño, Condition, Condición, Configuration, Configuración, Constante, Constant, Disque, Disk, Disco, Défaillance, Failures, Fallo, Echec, Failure, Fracaso, Emballage optimal, Bin packing, Garnissage, Packing, Relleno, Indépendance, Independence, Independencia, Informatique, Computer science, Informática, Inégalité, Inequality, Desigualdad, Optimisation, Optimization, Optimización, Ordinateur, Computer, Computadora, Partiel, Partial, Parcial, Poids, Weight, Peso, Polytope, Politope, Problème combinatoire, Combinatorial problem, Problema combinatorio, Rang, Rank, Rango, Réseau(arrangement), Array, Red, Système Steiner, Steiner system, Sistema Steiner, Séparation, Separation, Separación, Taille, Size, Talla, Théorie algorithme, Algorithm theory, Utilisation, Use, Utilización, Configuration Erdös, Erdös configuration, Plan emballage, Packing design, Système creux, Sparse system, Système triple, Triple system
Subject Geographic:
Allemagne, Germany, Alemania, Europe, Europa, Berlin, Berlín
Time:
1994, 1995, 1996, 1999
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
School of Information Technology and Engineering, University of Ottawa, Ottawa, Ont., K1N 6N5, Canada
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=14607552
Rights:
Copyright 2003 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Accession Number:
edscal.14607552
Database:
PASCAL Archive

Weitere Informationen

Combinatorial designs find 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, Math. Appl. 368 (1996) 227-254; Moura, Ph.D. Thesis, University of Toronto, 1999; Moura, Proc. Seventh Annu. European Symp. Prague, 1999, Lecture Notes in Computer Science, vol. 1643, Springer, Berlin, 1999, pp. 462-475; Wengrzik, Master's Thesis, Universität Berlin, 1995; Zehendner, Doctoral Thesis, Universität Augsburg, 1986). In this article, we study polytopes associated with t-(v,k,λ) packing designs and with m-sparse PSTSs. Subpacking and l-sparseness inequalities are introduced and studied. They can be regarded as rank inequalities for the independence systems associated with these designs. Conditions under which subpacking inequalities define facets are derived; in particular, those which define facets for PSTSs are determined. For m > 4, the l-sparseness inequalities with 2 ≤ l ≤ m are proven to induce facets for the m-sparse PSTS polytope; this proof uses extremal families of PSTSs known as Erdös configurations. Separation algorithms for these inequalities are proposed. We incorporate some of the sparseness inequalities in a polyhedral algorithm, and determine maximal 4-sparse PSTS(v), v ≤ 16. An upper bound on the size of m-sparse PSTSs is presented.