On the Diameter of a 2-Sum of Polyhedra
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916175980527616 |
|---|---|
| author | Borgwardt, Steffen Grewe, Weston Lee, Jon |
| author_facet | Borgwardt, Steffen Grewe, Weston Lee, Jon |
| contents | The study of the combinatorial diameter of a polyhedron is a classical topic in linear-programming theory due to its close connection with the possibility of a polynomial simplex-method pivot rule. The 2-sum operation is a classical operation for graphs, matrices, and matroids; we extend this definition to polyhedra. We analyze the diameters of 2-sum polyhedra, which are those polyhedra that arise from this operation. These polyhedra appear in matroid and integer-programming theory as a natural way to link two systems in a joint model with a single shared constraint and the 2-sum also appears as a key operation in Seymour's decomposition theorem for totally-unimodular matrices.
We show that the diameter of a 2-sum polyhedron is quadratic in the diameters of its summands. The methods transfer to a linear bound for the addition of a unit column to an equality system, or equivalently, to the relaxation of an equality constraint to an inequality constraint. Further, we use our methods to analyze the distance between vertices on certain faces of a 3-sum polyhedron. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02047 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Diameter of a 2-Sum of Polyhedra Borgwardt, Steffen Grewe, Weston Lee, Jon Optimization and Control 52B05, 52B40, 90C05 The study of the combinatorial diameter of a polyhedron is a classical topic in linear-programming theory due to its close connection with the possibility of a polynomial simplex-method pivot rule. The 2-sum operation is a classical operation for graphs, matrices, and matroids; we extend this definition to polyhedra. We analyze the diameters of 2-sum polyhedra, which are those polyhedra that arise from this operation. These polyhedra appear in matroid and integer-programming theory as a natural way to link two systems in a joint model with a single shared constraint and the 2-sum also appears as a key operation in Seymour's decomposition theorem for totally-unimodular matrices. We show that the diameter of a 2-sum polyhedron is quadratic in the diameters of its summands. The methods transfer to a linear bound for the addition of a unit column to an equality system, or equivalently, to the relaxation of an equality constraint to an inequality constraint. Further, we use our methods to analyze the distance between vertices on certain faces of a 3-sum polyhedron. |
| title | On the Diameter of a 2-Sum of Polyhedra |
| topic | Optimization and Control 52B05, 52B40, 90C05 |
| url | https://arxiv.org/abs/2311.02047 |