NDMI084 Introduction to approximation and randomized algorithms

Winter semester 2018/19

Petr Kolman, Jirí Sgall

Lectures take place on Mondays at 2 - 3:30 pm, lecture room S9.

Czech Lectures take place on Fridays at 9 - 10:30 pm, lecture room S4, and are given by Jiří Sgall.

Lecture notes by J. Sgall (in Czech)

Syllabus

This course covers techniques for design and analysis of algorithms, demonstrated on concrete combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design algorithms that finds an optimal solution fast. In such a case we study approximation algorithms that work faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness in design of (approximation and other) algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable. Recommended for the 3rd year.

Covered topics

• October 1
  • Introduction.
  • Randomized protocol for computing the average salary.
  • Optimization and NP-optimization problems.
• October 8
  • Approximation algorithm and ratio [WS 1.1, V1].
  • TSP - limits on approximation in the general setting.
  • Metric TSP - 2-approximation for the metric TSP, Christofides 1.5-approximation [WS 2.4, V 3.2].
  • Discrete probability - review of elementary definitions and properties (see Notes on probability by J. Matousek).
• October 15
  • Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
  • Contention resolution in a distributed system - randomized protocol [KT 13.1].
  • Randomized minimum cut algorithm - sketch of the algorithm [KT 13.2].
• October 22
  • Randomized minimum cut algorithm - analysis [KT 13.2].
  • Scheduling on identical machines - local search [WS 2.3].
• October 29
  • Scheduling on identical machines - greedy (list scheduling, longest processing time first), online [WS 2.3].
  • Greedy algorithms for bin packing (first fit, best fit, any fit, online) [WS 3.3, V 9].
• November 5
  • Greedy algorithm for edge disjoint paths in graphs [KT 11.5].
  • Greedy algorithm for paths in graphs with capacities [KT 11.5].
• November 12
  • Randomized algorithms for satisfiability [WS 5.1-5.5, V 16].
    
    • Ssimple 1/2-approximation algorithm for MAX SAT (RAND SAT ALG), 7/8-approximation algorithm for MAX-E3-SAT.
    • Biased randomized approximation algorithm.
    • Approximation based on linear programming relaxation.
• November 19
  • Choosing the better of two solutions - 3/4 approximation for MAX SAT [WS 5.5].
  • Derandomization of RAND SAT ALG for MAX SAT by the method of conditional expectation [WS 5.3].
  • Algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V 13-14].
    
    • The greedy algorithm and its analysis using dual linear program.
• November 26
  • Algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V 13-14].
    
    • The primal algorithm, the dual algorithm, the primal-dual algorithm.
  • Parallel algorithm for maximum independent set problem [MR 12.3, also nice notes by Eric Vigoda at http://www.cc.gatech.edu/~vigoda/7530-Spring10/MIS.pdf].
• December 3
  • Parallel algorithm for maximum independent set problem, contd. Derandomization - sketch. [MR 12.3, the notes by E. Vigoda].
  • Hashing [MR 8.4, MU 13.3].
• December 10
  • Hashing [MR 8.4, MU 13.3].
  • Dynamic dictionary with expected constant time per operation.
  • Static dictionary with constant time per lookup in the worst case.
  • Randomized testing of matrix multiplication in linear time [MR 7.1, MU 1.3].
• December 17
  • Randomized testing of polynomial identities [MR 7.1, MU 1.3].
  • Testing the existance of perfect matchings in bipartite and general graphs [MR 7.3, 12.4].
• January 7, 2019
  • Parallel randomized algorithm for a perfect matching [MR 7.3, 12.4].

Textbooks

There is no required textbook but the material presented in the course is covered by several good books.

[WS] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.

[MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.

[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.

[KT] J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.

Other courses on approximation or randomized algorithms

• Approximation Algorithms by Chandra Chekuri
• Approximation Algorithms and Approximability by Mohammad R. Salavatipour
• Approximation Algorithms by Anupam Gupta and R. Ravi