For the first part, see the web page maintained by Leen Stougie.
·
Week
6: Probabalistic Method (part 2) .
Lecture notes here.
Exercises: Problems 5.7, 5.8, 5.10
·
Week
7: Randomized PTAS for Euclidean TSP.
Lecture notes here. Lecture notes by Goemans on Karp’s algorithm here .
Exercises: See notes
·
Week
8: Approximate Counting.
Lecture notes here.
Exercises: See notes
·
Week
9: Randomized Rounding.
Lecture notes here.
Exercises: See notes
Please,
send your solutions to the exercises before 24th December to r.a.sitters@vu.nl
.