Timeline for Complexity of finding one vertex of a nonempty polytope
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2021 at 21:11 | comment | added | Hans | Would you be interested in taking a look at this problem of convex polytope containment mathoverflow.net/q/385579/32660? | |
| May 10, 2019 at 10:14 | vote | accept | guigux | ||
| May 10, 2019 at 9:07 | comment | added | Dima Pasechnik | see the edit for something that is probably close to optimal... | |
| May 10, 2019 at 9:06 | history | edited | Dima Pasechnik | CC BY-SA 4.0 |
an algorithm added
|
| May 9, 2019 at 14:03 | comment | added | Dima Pasechnik | probably there is a reason that simplex is fast in Phase I, some kind of general position situation that makes pivoting fast. | |
| May 9, 2019 at 12:43 | comment | added | guigux | It seems that the approach proposed by Rahul in the same question is exactly what I suggested above, I would happily welcome any reference in some text book that describes that approach. | |
| May 9, 2019 at 12:41 | comment | added | guigux | I also get stuck around the same problem as Dylan Phase 1 adds slack variables and work with an LP in canonical form, for which a BFS is known, while I want a simple method that finds a vertex in the form $P=\{x:Ax\leq b\}$ that takes advantage of the knowledge of a point $x_0 \in P$ | |
| May 9, 2019 at 12:32 | comment | added | guigux | Hi Dima, yes,you' re right, this problem is related to Phase 1. However, I cannot accept your answer for 2 reasons: In my understanding, the typical (textbook) way to solve Phase 1 is to use simplex iterations, starting from a basic feasible solution for a modified problem. I am interested in complexity, so I would like to avoid the simplex... | |
| May 8, 2019 at 23:05 | history | edited | j.c. | CC BY-SA 4.0 |
link to answer, not user page
|
| May 8, 2019 at 21:58 | history | answered | Dima Pasechnik | CC BY-SA 4.0 |