Διάλεξη 15/4: Πιθανοτικοί Αλγόριθμοι ΙI
- Πιθανοτικοί αλγόριθμοι: πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (γρήγορη επανάληψη) και 3-SAT (δείτε ακόμη και αυτές τις διαφάνειες για το 3-SAT), secretary problem, prophet inequalities (δείτε ακόμη εδώ για secretary problems και prophet inequalities), η πιθανοτική μέθοδος (απλά παραδείγματα εφαρμογής σε max-cut και maximum independent set), Lovasz Local Lemma και εφαρμογή στην ικανοποιησιμότητα k-SAT, Chernoff-Hoeffding bounds, set balancing, τυχαία δειγματοληψία.
Προτεινόμενη μελέτη:
- Διαφάνειες (ενημερωμένες).
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (ενότητες 3.2, 4.1, 4.2, 4.3, 5.1, 5.2 και 5.5).
- M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (Ενότητες 3.1-3.3, 4.1-4.4, 6.1, 6.2, 6.4, 6.7 και 7.1).
Προτάσεις για περαιτέρω μελέτη: Δυστυχώς, για τεχνικούς λόγους, δεν
κατέστη δυνατή η βιντεοσκόπηση της διάλεξης.