Sumários
Probabilistic method and a 3/4-approx randomized algorithm for MAX-SAT
30 maio 2018, 11:00 • Alexandre Francisco
MAX-SAT case study: from using probabilistic method to determining a 3/4-approximation randomized algorithm. [MR 5.2]
Lab 12
29 maio 2018, 12:30 • Alexandre Francisco
Exercises about string matching, suffix trees and suffix arrays. Exercise on the probabilistic method and its application on the max-cut problem.
Probabilistic method and randomized algorithms
29 maio 2018, 11:00 • Alexandre Francisco
Probabilistic method, introduction, motivation and limitations. Probabilistic method and randomized algorithms. Probabilistic method and the MAX-SAT problem. Approximation algorithms and performance ratios. [MR 5.1 and 5.2]
Fully polynomial randomized approximation schemes
23 maio 2018, 11:00 • Luís Manuel Silveira Russo
The Monte Carlo method for counting, pi and assignments of DNF formulas, Cap 10 [MU05].