Timeline for How do you tell if a system of linear inequalities has a solution?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 1, 2012 at 15:39 | comment | added | Emil Jeřábek | @Igor: The optimum is attained at a vertex of the polytope defined by the program, which is a solution of a linear system consisting of a subset of the inequalities turned into equalities. As such, it is polynomially bounded (in terms of bit-length of the numerator and denominator, i.e., logarithmic height). | |
| Apr 1, 2012 at 15:19 | comment | added | Igor Rivin | I almost put that comment into my response, but then I started thinking about getting estimates on the biggest possible size of optimum, and decided that it is a little trickier than it looks... | |
| Apr 1, 2012 at 10:15 | comment | added | Emil Jeřábek | You can compute the optimum of a linear program by using binary search on feasibility of the program together with an added linear constraint, hence feasibility testing is computationally about as complicated as full-blown linear programming. | |
| Apr 1, 2012 at 5:27 | history | edited | Uday |
edited tags
|
|
| Apr 1, 2012 at 5:26 | history | edited | Uday |
edited tags
|
|
| Apr 1, 2012 at 0:57 | answer | added | Igor Rivin | timeline score: 10 | |
| Mar 31, 2012 at 22:20 | answer | added | Brian Borchers | timeline score: 9 | |
| Mar 31, 2012 at 21:41 | history | asked | user21816 | CC BY-SA 3.0 |