I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional packing and covering problems in nearly linear time, and how the algorithms are instantiations of the learning from experts abstract framework.Kale's thesis has an excellent presentation, but I find it very difficult to directly jump into the abstract framework, and I would prefer to start from an example of a simple problem for which it's absolutely obvious what to do, and then move to more general problems, progressively adding features to the algorithm and to its analysis.For example: How does Plotkin-Shmoys solve the linear programming relaxation of unweighted vertex cover? Weighted vertex cover? Set cover? Bipartite matching?What is the simplest example in which the Arora-Kale algorithm is doing something interesting? How does it compute the largest eigenvalue of the Laplacian of a graph? (Computing the largest eigenvalue of the Laplacian is equivalent to the problem of solving a weaker version of the Goemans-Williamson SDP relaxation of Max Cut, in which, instead of requiring each vector to be of length one, you want the sum of the squares of the norms to be |V|.)
Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers
ds.algorithms;approximation algorithms;linear programming;primal dual;semidefinite programming