Timeline for Short and slick proof of the strong duality theorem for linear programming
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2019 at 13:20 | comment | added | Magnus Lie Hetland | Ah, I guess a central point is the geometric interpretation in the previous lecture, which takes us back to the Simplex family of proofs: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf | |
| Jan 8, 2019 at 13:10 | comment | added | Magnus Lie Hetland | Trying to find something not-too-cumbersome myself, to show my students (so they don't have to just take strong duality on faith), and most of what I've come across is more in the too-cumbersome category. Just found an argument in notes from a class of Dan Spielman's, which is quite short and seemingly simple. Not sure if it's hiding some complexity, or if there's something missing? (Haven't examined it thoroughly enough to tell, yet.) cs.yale.edu/homes/spielman/BAP/lect12.pdf | |
| Oct 21, 2017 at 18:36 | comment | added | Kaveh | It seems that what I wanted is probably not possible. The Farkas uses the closedness of space which means there is probably no pure linear algebra proof. | |
| Nov 20, 2013 at 0:00 | answer | added | Louis | timeline score: 3 | |
| Nov 19, 2013 at 21:28 | comment | added | Kaveh | @cody, well, it seems essentially the same as the one in CLRS. It can be fine if you can express it in a slick linear algebra way (i.e. no sums). | |
| Nov 19, 2013 at 17:40 | comment | added | cody | Chapter 4 of the MIT online course web.mit.edu/15.053/www by Bradley, Hax, and Magnanti gives a reasonably short proof along these lines. Is this what you're looking for? | |
| Nov 19, 2013 at 13:02 | history | tweeted | twitter.com/#!/StackCompSci/status/402783987875471360 | ||
| Nov 19, 2013 at 9:39 | history | asked | Kaveh | CC BY-SA 3.0 |