LSE office hours & teaching

This page is an easier-to-edit adjunct to my official LSE page.

(Jump to Gregory Sorkin's home page.)


Prof. Sorkin's tentative office hours MT 2013-14 are as follows.  I will try to keep these updated, but if you plan to meet with me, please confirm with me by email first.
Tue  8 Oct  16.30-17.30
Tue 15 Oct  16.30-17.30   Thu 17 Oct 15.00-16.00
Tue 22 Oct  14.30-15.30   Wed 23 Oct 14.00-15.00
Wed 30 Oct  16.30-17.30
Wed  6 Nov  16.30-17.30   Thu  7 Nov 16.00-17.00
Wed 13 Nov  14.30-15.30
Tue 19 Nov  14.30-15.30
Wed 27 Nov  14.00-16.00
Wed  4 Dec  14.00-16.00
Wed 11 Dec  14.00-16.00


Michaelmas term 2013-14:
MG461 -- Quantitative Analysis in Management (weeks 7--9)

Lent term 2013-14:
OR437 -- Solving Unsolvable Problems: NP-completeness and how to cope with it

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:
Husfeldt, A Taxonomic Introduction to Exact Algorithms (pdf lecture notes)
- Williamson and Shmoys, 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)

- Fomin and Kratsch, Exact Exponential Algorithms
- Mitzenmacher and Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis
- Vazirani
, Approximation Algorithms