This page is an easier-to-edit adjunct to my official LSE page. (Jump to Gregory Sorkin's home page.)Office hours, MT 2011: Mondays 13.30--15.30 in NAB 3.19, and by appointment Teaching, MT 2011: OR414 -- Advanced Topics in Operational Research: Solving Unsolvable Problems Course content: Many problems, from the "Traveling Salesman Problem" to problems like 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 concepts (polynomial-time computation and NP-completeness), then explore various ways of coping with intractable problems: heuristics, approximation algorithms, average-case analysis, and relatively efficient exponential-time algorithms. Prerequisites: No formal prerequisites, but a good general knowledge of mathematics and a level of mathematical sophistication, including familiarity with proofs and abstract thinking. Formative work: Weekly exercises, discussed in seminars. Assessment: One piece of weekly coursework will be assessed, comprising 15% of the mark. The remaining 85% will be based on a formal 2.5-hour examination in Summer Term (3 questions of 4). Recommended reading: Online - Husfeldt, A Taxonomic Introduction to Exact Algorithms (pdf lecture notes) - 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) Books - Fomin and Kratsch, Exact Exponential Algorithms - Mitzenmacher and Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis - Vazirani, Approximation Algorithms |