CPSC 465: Topics in Algorithms
Fall 2005
Overview:
Introduction to the fundamental tools used in approximation algorithms; linear, convex,
and semi-definite programing; dynamic programming; and geometric tools. Recent progress
in the design of approximation algorithms for graph problems, combinatorial problems,
and other NP-hard optimization problems. Results on the hardness of approximation
based on probabilistically checkable proofs.
Office hours: TTh 2:30-3:30, AKW 405
Assignments
- Problem Set 1 due Thursday, September 22.
- Problem Set 2 due Thursday, October 6.
- Problem Set 3
- Problem Set 4 due Thursday, November 17.
- Problem Set 5 due Thursday, December 1.
Annoucements
-
10-05-06:
There is a Physics seminar on
"Spanning trees and random resistor networks in d dimensions"
by Nicholas Read
at 1 pm on Thursday,
October 6.
There is now quite some interest in Physics in
Combinatorial problems and it will be good for us to
see the Physics connection and their approach.
Instead of the regular lecture
tomorrow, the class will consist of this seminar.
The location is 56 SPL.
Note it is a good 10-15 minute walk from here.