26 April - 2 May
Section outline
-
Διάλεξη 28/4: Πιθανοτικοί Αλγόριθμοι ΙII - Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό
- Πιθανοτικοί αλγόριθμοι: Chernoff-Hoeffding bounds, set balancing, τυχαία δειγματοληψία.
- Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized (και deterministic) rounding για VLSI routing, Set Cover, Max-Cut.
Προτεινόμενη μελέτη:- Διαφάνειες για προσεγγιστικούς αλγόριθμους βασισμένους σε Γραμμικό Προγραμματισμό.
- D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 1.3-1.7, 5.1-5.2, 5.4-5.5, και 6.1-6.3.
- Σημειώσεις και σημειώσεις για την μέθοδο των conditional expectations (δείτε και το σχετικό λήμμα στο wikipedia).
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).