The notes
from the LP/SDP course have Ax ge b instead of Ax le b, but the idea
is really the same. Also, it has an example running the
algorithm for solving the Set Cover LP.
Rohit
Khandekar's thesis
makes great reading about solving convex programs using MW; so
does Satyen
Kale's thesis;
both have excellent survey chapters.
Relevant section of the
Arora-Hazan-Kale survey
about solving LPs.
Elad
Hazan
and Shai
Shalev-Shwartz present it using the equivalence to
Follow the Regularized Leader. We did not talk
about the latter connection, but you may see this as a HW
problem, time permitting.
Lecture 21. (Mar 13) The Centroid and Ellipsoid Algorithms
(draft
notes)
The Bertsemas-Vempala
paper on computing approximate centroids by random sampling, allowing the centroid algorithm to run in polynomial time.