Computers and Intractability
Spring 2013
Prof. David
Avis
Thurs
8:45-10:15
Research Bldg. 7 (formerly Enginering 10) Joho1
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 5, 2013