Computers and Intractability
Spring 2011
Prof. David
Avis
Thurs
8:45-10:15
Course home page
Assessment: See
Reports
and Grading
1. Each lecture has a mandatory reading assignment.
2. Students are required to submit 3 reports on
subjects that will be given
during lectures.
Topics: Subject to
revision.
The following topics are covered, each in two to four lectures.
1. The class of NP-complete
problems. Cook’s theorem and problem reductions. NP-hard problems.
2. Some NP-hard problems
arising in scheduling.
3. Introduction to linear
and integer programming.
4. Integer programming
formulations of some scheduling problems.
5. Solution of integer
programs and related software.
April 11, 2011