1. Approximation algorithms
(Sunday, September 23, 2007 - 17:55)
Approximation algorithms for vertex cover and set cover.
|
2. Approximation algorithms
(Sunday, September 30, 2007 - 17:30)
Approximation algorithm for shortest common superstring.
|
3. Approximation algorithms
(Sunday, October 7, 2007 - 17:30)
Approximation algorithm for metric TSP, FPTAS for knapsack.
|
4. Approximation algorithms
(Sunday, October 14, 2007 - 17:35)
Approximation algorithms for weighted vertex cover and hitting set.
|
5. Approximation algorithms
(Sunday, November 11, 2007 - 17:35)
Semidefinite programming, approximation algorithm for MAX-CUT, coloring a 3-colorable graph.
|
6. Randomized algorithms
(Sunday, November 11, 2007 - 17:45)
Randomized algorithms for verifying the correctness of matrix product, verifying the equivalence of long strings, zeroes of multivariate polynomials, verifying the equivalence of branching programs.
|
7. Randomized algorithms
(Sunday, November 18, 2007 - 17:50)
Randomized algorithm for minimum cut, randomized primality testing.
|
8. Randomized algorithms
(Sunday, November 18, 2007 - 18:00)
Randomized algorithms for all-pairs distances, Boolean matrix product witnesses, all-pairs shortest paths.
|
9. Randomized algorithms
(Sunday, November 25, 2007 - 18:20)
Randomized linear-time algorithm to find minimum spanning trees.
|
10. Derandomization
(Sunday, November 25, 2007 - 18:25)
Method of conditional probabilities, method of small sample spaces.
|
11. Satisfiability problem
(Sunday, December 2, 2007 - 18:25)
Reduction from Japanese puzzles and Eternity game to SAT and from MAX-CUT to MAX-SAT.
|
12. Algorithms for SAT
(Sunday, December 2, 2007 - 18:25)
DPLL, PPSZ and random walk algorithms.
|
13. Approaches to Proving Upper Bounds for NP-hard Problems
(Sunday, February 17, 2008 - 18:40)
Splitting, random evaluation order, local search, dynamic programming, reduction to easy problem, random reduction to easy problem, clever enumeration.
|
14. Linear Programming
(Sunday, February 24, 2008 - 18:35)
Flows in networks, maximum bipartite matching, duality, simplex algorithm.
|
15. Polynomial Algorithm for LP
(Sunday, March 9, 2008 - 14:55)
Karmarkar's polynomial algorithm for linear programming.
|
16. Dynamic Programming
(Sunday, March 9, 2008 - 18:35)
Edit distance, knapsack, chain matrix multiplication, shortest reliable paths, all-pairs shortest paths, TSP, independent sets in trees.
|
17. Greedy Algorithms
(Sunday, March 16, 2008 - 18:35)
Activity-selection, Huffman encoding, set cover, vertex cover, SAT local search.
|
18. Maximum Flow
(Sunday, March 16, 2008 - 18:55)
Ford-Fulkerson method, preflow-push method, lift-to-front algorithm.
|
19. Multiflow
(Sunday, March 23, 2008 - 18:30)
|
20. Maximum Matching
(Sunday, March 30, 2008 - 19:00)
Augmenting paths, bipartite matching, general case.
|
21. Online algorithms
(Sunday, April 6, 2008 - 18:30)
Online algorithms for paging and set cover.
|
Русский
English