Finding Short Paths on Simple Polytopes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910109924327424 |
|---|---|
| author | Black, Alexander E. Steiner, Raphael |
| author_facet | Black, Alexander E. Steiner, Raphael |
| contents | We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanità. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we show this is NP-hard already for fractional knapsack polytopes. By applying an additional polyhedral construction, we show that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem by Kaibel and Pfetsch. Finally, on the positive side we show that every polytope has a small, simple extended formulation for which a linear length path may be found between any pair of vertices in polynomial time building upon a result of Kaibel and Kukharenko. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05482 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finding Short Paths on Simple Polytopes Black, Alexander E. Steiner, Raphael Data Structures and Algorithms Combinatorics Optimization and Control 90C05, 90C27, 90C35, 90C49, 90C57, 90C60 We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanità. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we show this is NP-hard already for fractional knapsack polytopes. By applying an additional polyhedral construction, we show that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem by Kaibel and Pfetsch. Finally, on the positive side we show that every polytope has a small, simple extended formulation for which a linear length path may be found between any pair of vertices in polynomial time building upon a result of Kaibel and Kukharenko. |
| title | Finding Short Paths on Simple Polytopes |
| topic | Data Structures and Algorithms Combinatorics Optimization and Control 90C05, 90C27, 90C35, 90C49, 90C57, 90C60 |
| url | https://arxiv.org/abs/2603.05482 |