Postgraduate lesson: Combinatorial Optimization
Lectures 2011-12
link to lecture
<
2-11-11 Lecture 1: models LP, IP, Task Assignment, (1) TSP
4-11-11 Lecture 2: models LP, IP, Task Assignment, (2) TSP
9-11-11 Lecture 3: Integer Programming - Relaxation
11-11-11 Lecture 4: Branch And Bound (1)
18-11-11 Lecture 5: Branch And Bound (2)
23-11-11 Lecture 6: a Branch And Bound for the Hamiltonian Path
23-11-11 Lecture 7: Heuristics
25-11-11 Lecture 8: Approximation Algorithms
7-12-11 Lecture 9: Covering and Packing
9-12-11 Lecture 10: TSP is Non Approximated
9-12-11 Lecture 10: MIS and applications
14-12-11 Lecture 11: The MIS - Heuristics
14-12-11 Lecture 11: A D/2 approximation algorithm for MIS
16-12-11 Lecture 12: The 0-1 Knapsack problem
16-12-11 Lecture 12: Absolute Approximation
21-12-11 Lecture 13: Dynamic Programming
21-12-11 Lecture 13: FPTAS for the 0-1 knapsak
23-12-11 Lecture 14: FPTAS for the Sub-Set Sum problem
11-01-12 Lecture 15: Approximation Classes
13-01-12 Lecture 16: Local Search
18-01-12 Lecture 17: PLS-completeness
20-01-12 Lecture 18: Simulated annealing
25-01-12 Lecture 19: Simulated annealing-applications
27-01-12 Lecture 20: Stable configurations in Neural Networks
xx-xx-xx Lecture 11: weighted bipartitioning (2-approximation)
xx-xx-xx Lecture 12: weighted bipartitioning (2+epsilon-approximation)
Current Lesson