Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Линейное программирование
Санкт-Петербург / весна 2011, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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.

Дата и время Название Место Материалы
16 апреля
17:20–18:55
Лекция 1, лекция ПОМИ РАН видеофайлы
16 апреля
19:05–20:40
Лекция 2, лекция ПОМИ РАН видеофайлы
17 апреля
11:15–12:50
Лекция 3, лекция ПОМИ РАН видео
17 апреля
13:00–17:35
Лекция 4, лекция ПОМИ РАН видеофайлы
17 апреля
15:35–17:10
Лекция 5, лекция ПОМИ РАН видеофайлы
23 апреля
17:20–18:55
Лекция 6, лекция ПОМИ РАН видеофайлы
23 апреля
19:15–20:50
Лекция 7, лекция ПОМИ РАН видеофайлы
24 апреля
11:15–12:50
Лекция 8, лекция ПОМИ РАН видеофайлы
24 апреля
13:00–14:35
Лекция 9, лекция ПОМИ РАН видеофайлы
24 апреля
15:35–17:10
Лекция 10, лекция ПОМИ РАН видеофайлы