TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1996

COGA 5-Wheel

Page Content

to Navigation

Preprints 1996

Transitive Packing
Citation key Report-508-1996
Author Rudolf Müller and Andreas S. Schulz
Year 1996
Number 508
Note appeared in IPCO'96
Institution Technische Universität Berlin, Institut für Mathematik
Abstract This paper is intended to give a concise understanding of the facial structure of previously separately investigated polyhedra. We introduce the notion of transitive packing and the transitive packing polytope and give cutting plane proofs for huge classes of valid inequalities of this polytope. We introduce generalized cycle, generalized clique, generalized antihole, generalized antiweb, generalized web, and odd partition inequalities. These classes subsume several known classes of valid inequalities for several of the special cases but also give many new inequalities for several others. For some of the classes we also prove a nontrivial lower bound for their Chvátal rank. Finally, we relate the concept of transitive packing to generalized (set) packing and covering as well as to balanced and ideal matrices.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe