Not available in 2014/15
OR437 Half Unit
Solving Unsolvable Problems: NP- completeness and how to cope with it
This information is for the 2014/15 session.
Teacher responsible
Prof Gregory Sorkin NAB 3.19
Availability
This course is available on the MSc in Management Science (Decision Sciences) and MSc in Management Science (Operational Research). This course is available with permission as an outside option to students on other programmes where regulations permit.
Pre-requisites
A level of mathematical sophistication, including comfort with proofs and familiarity with limits, permutations, factorials, binomial coefficients, and rudimentary probability including expectations and independence. If in doubt, please consult the instructor or attend the first lecture.
Course content
Many problems, from the "Travelling Salesman Problem" to train scheduling, are easy to state but hard to solve, in a mathematically well-defined sense. In practical operations research, though, one must solve such problems, and the issues involved are mathematically interesting. The course will introduce the underlying computational concepts (polynomial-time computation and NP-completeness); introduce canonical problem models including graph problems and formula satisfiability; and explore various ways of addressing these problems, including heuristics, randomized and approximation algorithms, average-case analysis, and relatively efficient exponential-time algorithms.
Teaching
20 hours of lectures and 13 hours and 30 minutes of seminars in the LT. 2 hours of lectures in the ST.
Indicative reading
Shmoys and Williamson, The Design of Approximation Algorithms (Cambridge Univ. Press book, free e-version)
Sinclair, Randomness and Computation (U.C. Berkeley lecture notes, by kind permission of the author)
Print books
Fomin and Kratsch, Exact Exponential Algorithms
Mitzenmacher and Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Assessment
Exam (85%, duration: 2 hours and 30 minutes) in the main exam period.
Coursework (15%) in the LT.
Key facts
Department: Management Science Group
Total students 2013/14: 4
Average class size 2013/14: 4
Controlled access 2013/14: No
Lecture capture used 2013/14: No
Value: Half Unit
Personal development skills
- Self-management
- Team working
- Problem solving
- Communication
- Application of numeracy skills
- Specialist skills