Computers and Intractability                 Spring 2010

Prof. David Avis                          Thurs 8:45-10:15          Course home page

Assessment:

Students are required to submit reports on subjects that will be given during lectures. Some reports will involve using course software.

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.





March 17, 2010