Timeline for Is the Simplex Method still polynomial when all inequalities are through the origin?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 15, 2019 at 21:51 | history | suggested | VS. | CC BY-SA 4.0 |
Terminology+link.
|
| Oct 15, 2019 at 19:47 | review | Suggested edits | |||
| S Oct 15, 2019 at 21:51 | |||||
| Mar 14, 2019 at 11:54 | comment | added | Bodo Manthey | I have doubts if smoothed analysis helps here. If you perturb the constraints as it is done in smoothed analysis, then none of them will go through the origin. | |
| Apr 24, 2012 at 21:45 | comment | added | user21816 | I looked into it more - you're completely right, and now I'm trying to remember why I was so sure Simplex was strongly polynomial in the first place. I may have found one of the cases on which it's exponential. I found a source that says there are no known strongly-polynomial linear programming algorithms, and the existence of such an algorithm is a major open question. Thanks for your help! | |
| Apr 24, 2012 at 21:43 | vote | accept | user21816 | ||
| Apr 24, 2012 at 21:29 | history | answered | Pascal Maillard | CC BY-SA 3.0 |