Binary Cyclic Transversal Polytopes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914745955647488 |
|---|---|
| author | Frede, Jonas Kaibel, Volker Merkert, Maximilian |
| author_facet | Frede, Jonas Kaibel, Volker Merkert, Maximilian |
| contents | With every family of finitely many subsets of a finite-dimensional vector space over the Galois-field with two elements we associate a cyclic transversal polytope. It turns out that those polytopes generalize several well-known polytopes that are relevant in combinatorial optimization, among them cut polytopes as well as stable set and matching polytopes. We introduce the class of lifted odd-set inequalities and prove results demonstrating their strength. In particular, we show that they suffice to describe cyclic transversal polytopes if the union of the sets in the family has rank at most two. We also describe extended formulations for cyclic transversal polytopes and introduce a special relaxation hierarchy for them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06088 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Binary Cyclic Transversal Polytopes Frede, Jonas Kaibel, Volker Merkert, Maximilian Combinatorics 05C21, 52B12, 90C10, 90C27, 90C57 With every family of finitely many subsets of a finite-dimensional vector space over the Galois-field with two elements we associate a cyclic transversal polytope. It turns out that those polytopes generalize several well-known polytopes that are relevant in combinatorial optimization, among them cut polytopes as well as stable set and matching polytopes. We introduce the class of lifted odd-set inequalities and prove results demonstrating their strength. In particular, we show that they suffice to describe cyclic transversal polytopes if the union of the sets in the family has rank at most two. We also describe extended formulations for cyclic transversal polytopes and introduce a special relaxation hierarchy for them. |
| title | Binary Cyclic Transversal Polytopes |
| topic | Combinatorics 05C21, 52B12, 90C10, 90C27, 90C57 |
| url | https://arxiv.org/abs/2404.06088 |