|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
16 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
On the facet pivot simplex method for linear programming II: a linear iteration bound | | Yaguang Yang
; | | Date: |
1 Jan 2022 | | Abstract: | The Hirsch Conjecture stated that any $d$-dimensional polytope with n facets
has a diameter at most equal to $n - d$. This conjecture was disproved by
Santos (A counterexample to the Hirsch Conjecture, Annals of Mathematics,
172(1) 383-412, 2012). The implication of Santos’ work is that all {it vertex}
pivot algorithms cannot solve the linear programming problem in the worst case
in $n - d$ vertex pivot iterations.
In the first part of this series of papers, we proposed a {it facet} pivot
method. In this paper, we show that the proposed facet pivot method can solve
the canonical linear programming problem in the worst case in at most $n-d$
facet pivot iterations. This work was inspired by Smale’s Problem 9
(Mathematical problems for the next century, In Arnold, V. I.; Atiyah, M.; Lax,
P.; Mazur, B. Mathematics: frontiers and perspectives, American Mathematical
Society, 271-294, 1999). | | Source: | arXiv, 2201.00193 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER