City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Linear programming
Saint Petersburg / spring 2011, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Linear programming (LP) was introduced in the fourth decade of the 20th century and was initially regarded as a branch of optimization theory. Quite rapidly LP had become a popular method for solving economic and planning problems with variables ranging over the set of reals. In certain cases it turned out possible to adapt LP to discrete problems as well. However, a systematic study of LP approaches in combinatorics had started only a few decades later. This area was pioneered by Jack Edmonds, whose research in polyhedral combinatorics vastly improved our knowledge of connections between combinatorial and linear problems.

The course has multiple goals.

First, we shall study the very foundations of LP including linear separability and duality. We shall discuss the ellipsoid method and use it to derive a polynomial-time solvability of general LP problems.

Second, a great deal of attention will be payed to connections between LP and discrete programming, combinatorics, and optimization. The key notions here are that of total unimodularity and total dual integrality. We shall construct examples of such good linear programs for a large number of combinatorial problems.

A survey of some more recent techniques will also be given. Submodularity and its connection to matroids will be discussed. We shall learn basic facts on submodular flows. The latter powerful tool will allow us to derive numerous consequences. Some of them are pretty elementary (like the theorems of Ford-Fulkerson or Dilworth). Others are more involved (like Nash-Williams' theorem that claims existence of a k-connected directed orientation of every 2k-connected undirected graph).

Finally, the elements of semi-definite programming (SDP) and its use in approximate algorithms will be covered. We shall consider MAX-CUT, which is a famous for its SDP-based approximation.

Date and time Class|Name Venue|short Materials
16 April
17:20–18:55
Лекция 1, Lecture ПОМИ РАН video,  files
16 April
19:05–20:40
Лекция 2, Lecture ПОМИ РАН video,  files
17 April
11:15–12:50
Лекция 3, Lecture ПОМИ РАН video
17 April
13:00–17:35
Лекция 4, Lecture ПОМИ РАН video,  files
17 April
15:35–17:10
Лекция 5, Lecture ПОМИ РАН video,  files
23 April
17:20–18:55
Лекция 6, Lecture ПОМИ РАН video,  files
23 April
19:15–20:50
Лекция 7, Lecture ПОМИ РАН video,  files
24 April
11:15–12:50
Лекция 8, Lecture ПОМИ РАН video,  files
24 April
13:00–14:35
Лекция 9, Lecture ПОМИ РАН video,  files
24 April
15:35–17:10
Лекция 10, Lecture ПОМИ РАН video,  files