NDMI084 - Introduction to approximation and randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů

Jiří Sgall

Fall 2015 - Tuesday 15:40 in S4

Česká cvičení se konají jednou za 14 dnů po přednášce od 17:20 v S8, vede je Martin Böhm

English recitation sections are replaced by biweekly office hours by Martin Böhm

Předchozí běh přednášky v r. 2014 [previous year, in Czech only]

Poznámky k přednášce [lecture notes in Czech]

Covered topics

• 1. (6. 10.)
  
  • randomized protocol for computing the average salary
  • definition: optimization and NP-optimization problems, approximation algorithm and ratio [WS 1.1, V1]
• 2. (13. 10.)
• traveling salesperson problem (TSP), kostrový 2-approximation algorithm [WS 2.4]
• traveling salesperson problem (TSP), Christofides 1.5-approximation algorithm [WS 2.4, V 3.2]
• definition: probability spaces [MU 1.2]
• models of randomized computation [MR 1.5]
  
• definition: expectation, its linearity [MU 2.1]
• 3. (20. 10.)
• randomized conflict resolution in distributed systems [KT 13.1, MR 12.5]
• Quicksort as a randomized algorithm [MU 2.5, MR 1, KT 13.5]
• greedy algorithms for scheduling on identical machines [WS 2.3, KT 11.1]
• 4. (27. 10.)
• online algorithms and local search for scheduling [WS 2.3]
• greedy algorithms for bin packing [WS 3.3, V 9]
• 5. (3. 11.)
  
• greedy algrotihms for disjoint paths in graphs [KT 11.5]
• greedy algrotihms for disjoint paths in graphs with capacities [KT 11.5]
• randomized algorithms for satisfiability [WS 5.1-5.5, V 16]
  
• simple 1/2-approximation algorithm for MAXSAT, 7/8-approximation algorithm for MAX-E3-SAT
• 6. (10. 11.)
  
• randomized algorithms for satisfiability [WS 5.1-5.5, V 16]
  
• 3/4-approximation algorithm for MAXSAT
• derandomization by the method of conditional probabilities
  
• vertex cover approximation from linear programming
• 7. (24. 11.)
  
• algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V 13-14]
  
• rounding of the linear program solution
• primal-dual algorithm
• the greedy algorithm and its analysis using dual linear program
• 8. (1. 12.)
• universal systems of hash functions and their use [MR 8.4, MU 13.3]
  
• dynamic dictionary with expected constant time per operation [MR 8.4, MU 13.3.3]
  
• static dictionary with expected constant time per lookup in the worst case [MR 8.5, MU 13.3.3]
• 9. (8. 12.)
  
• fast parallel randomized algorithm for maximal independent set in graphs [MR 12.3, also nice notes by Eric Vigoda at http://www.cc.gatech.edu/~vigoda/7530-Spring10/MIS.pdf]
• derandomization using pairwise independent variables
• 10. (15. 12.)
  
• randomized testing of matrix multiplication in linear time [MR 7.1, MU 1.3]
  
• randomized testing of polynomial identities [MR 7.2, MU 1.1]
• 11. (22. 12.)
• cake cutting [S. Even, A. Paz: A note on cake cutting. Discrete Applied Mathematics 7(3):285-296, 1984. doi:10.1016/0166-218x(84)90005-2; a nice book with more material is  J. Robertson, W. Webb: Cake-Cutting Algorithms: Be Fair if You Can, A K Peters, 1998]
  
• 12. (5. 1.)
  
• a fast parallel randomized algorithm for perfect matching in bipartite and general graphs [MR 7.3, 12.4]
• 13. (12. 1.)
  
• a fast parallel randomized algorithm for perfect matching in bipartite and general graphs [MR 7.3, 12.4]
• 2-approximation algorithm for scheduling on unrelated machines [V 17, WS 11.1]

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.

Sylabus [Detailed syllabus in Czech]

Přednáška probírá středně pokročilé techniky pro návrh a analýzu algoritmů a ilustruje je na konkrétních kombinatorických problémech. Pro mnohé optimalizační problémy je obtížné navrhonout algoritmy, které je vyřeší optimálně a zároveň rychle (např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Často pro návrh algoritmů (aproximačních i jiných) používáme náhodnost, což umožňuje řešit některé úlohy efektivněji nebo řešit úlohy jinak neřešitelné. Doporučeno pro 3. ročník bakalářského studia.

Probírané techniky:

• Hladový algoritmus jako metoda pro návrh aproximačních a online algoritmů
• Použití lineárního programování pro návrh aproximačních algoritmů
• Po dvou nezávislé náhodné proměnné
• Odstranění náhodnosti metodou podmíněných pravděpodobností
• Lokální prohledávání

Probírané problémy a algoritmy:

• Rozvrhování a hledání disjunktních cest v grafu - hladové algoritmy
• Problém obchodního cestujícího a vrcholové pokrytí - jednoduché kombinatorické aproximační algoritmy
• Množinové pokrytí - hladový algoritmus, použití lineárního programování
• Splnitelnost (MAX-SAT) - použití lineárního programování, náhodné zaokrouhlování, derandomizace
• Hashování dynamické a statické - pravděpodobnostní algoritmy, po dvou nezávislé náhodné proměnné
• Největší řez v grafu - aproximace pomocí lokálního prohledávání
• Maximální nezávislá množina v grafu - rychlý pravděpodobnostní paralelní algoritmus
• Verifikace maticových rovnic - pravděpodobnostní protokol

Textbooks:

[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.