Introduction to approximation and randomized algorithms
Petr Kolman, Jirí Sgall
Lectures take place every week from 2 pm in S4.
Česká cvičení
se konají jednou za 14 dnů v pondělí od 14:00, vede je Martin Böhm.
English classes (recitations)
take place once in two weeks on Monday at 2 pm and are led by Martin Böhm.
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 4
- Introduction.
- Randomized protocol for computing the average salary.
- Optimization and NP-optimization problems,
approximation algorithm and ratio [WS 1.1, V1].
- TSP - limits on approximation in the general setting, 2-approximation
for the metric TSP [WS 2.4].
- October 11
- 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).
- Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
- October 18
- Contention resolution in a distributed system - randomized protocol [KT 13.1].
- Randomized minimum cut algorithm [KT 13.2].
- October 25
- Scheduling on identical machines - local search, greedy (list scheduling, longest processing time first), online [WS 2.3].
- November 1
- Greedy algorithms for bin packing (first fit, best fit, any fit, online) [WS 3.3, V 9].
- Greedy algorithm for edge disjoint paths in graphs [KT 11.5].
- Greedy algorithm for paths in graphs with capacities [KT 11.5].
- November 8 - no lectures, Dean's Sports Day
- November 15
- Greedy algorithm for paths in graphs with capacities - contd. [KT 11.5].
- Randomized algorithms for satisfiability [WS 5.1-5.5, V 16]
- simple 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 22
- MAX SAT approximation based on linear programming relaxation, contd. [WS 5.4]
- Choosing the better of two solutions - 3/4 approximation for MAX SAT [WS 5.5]
- Derandomization of RAND SAT ALG by the method of conditional expectation [WS 5.3]
- November 22
- From November 22 till the end of the semester, the lectures are given
by Jirka Sgall.
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.
For introduction to Linear Programming whose elementary knowledge is expected
in this course, we recommend the first three chapters of the textbook
Understanding and Using Linear Programming by J. Matousek and B. Gärtner (a
preliminary Czech version is available as Lineární programování a
lineární algebra pro informatiky).
Other courses on approximation or randomized algorithms