Advanced Algorithms

Slides

II. Linear Programming, Slide 26: In the equation with b=(.), b_3 should be replaced b_4 (corrected in the PDF above). Thanks to Shiv Godhia.
II. Linear Programming, Illustration of how the auxiliary linear program enlargens the feasible region PDF . Thanks to Lawrence Chonavel for suggesting this.
III. Approximation Algorithms. An update on the exercise questions PDF . Thanks to Robert Hönig for suggesting an improved approximation algorithm based on vertex coloring.
IV. Approximation Algorithms / Subset-Sum. On slide 10.1, L'_i should be replaced by L_i. Thanks to Nitish Bala.
IV. Approximation Algorithms / Scheduling. On slide 18, 3/2 C_{max} should be replaced by C_{max}^{*}. Thanks to Nitish Bala.
IV. Approximation Algorithms / Scheduling. Regarding the exercise on slide 21, the correct solution is not among the three options. Thanks to Sam Kerr.
IV. Approximation Algorithms / Scheduling. There were two small typos on the (non-examinable) Slide 25: Ceilings should be floors, and the summation should go from b to b^2. Thanks to Yu Chen.

If you have any questions or comments on the slides, feel free to send an email to the lecturer.

Miklos Ajtai, Janos Komlos, Endre Szemeredi. Sorting in c log n parallel steps, Combinatorica 3(1):1-19, 1983.
James Aspnes, Maurice Herlihy, Nir Shavit. Counting Networks, Journal of the ACM 41(5):1020-1048, 1994.
Costas Busch, Maurice Herlihy. A Survey on Counting Networks, Proceedings of the 1st Workshop on Distributed Data and Structures, pages 13-20, 1998.
Vasek Chvatal. Lecture Notes on the AKS Sorting Network, PDF
Shlomo Hoory, Nathan Linial, Avi Wigderson. Expander Graphs and their Applications, Bulletin of the American Mathematical Society, 43(4):439-561, 2006.

Robert G. Bland. New finite pivoting rules for the simplex method, Mathematics of Operations Research 2, (2):103-107, 1977.
Daniel A. Spielman and Shang-Hua Teng. Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time, Journal of the ACM, 51(3):385-463, 2004.

Vasek Chvatal, William J. Cook, George B. Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson. Solution of a Large-Scale Traveling-Salesman Problem, 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 7-28, 2010.
G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson, Solution of a Large-Scale Traveling-Salesman Problem, Operation Research 2:393-410, 1954.
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011. (electronic version available here)