Теоретический семинар (весна 2018)

Алгоритм для Target Set Selection с константными ограничениями на пороговые значения

Время: 22 февраля, 18:30

Место: СПбАУ РАН

Докладчик: Данил Сагунов

 

Описание:

 

Мы закончим рассматривать экспоненциальный алгоритм для Minimum Perfect Target Set

и покажем, как этот алгоритм изменяется в случае решения задачи Target Set Selection.

 

 

Материалы доклада 15 февраля. 

Название: Алгоритм для Target Set Selection с константными ограничениями на пороговые значения

Время: 15 февраля, 16:30

Место: ПОМИ РАН, ауд. 402

Докладчик: Данил Сагунов

 

Описание:

 

Мы рассмотрим NP-трудную задачу Target Set Selection, представляющую собой модель распространения мнения в социальных сетях.

Будет предложен точный алгоритм, позволяющий решать задачу быстрее 2^n, если пороговые значения распространения ограничены

некоторой фиксированной константой.

В докладе будет доказана экспоненциальная нижняя оценка на размер свободных бинарных диаграмм решений (FBDD) для выполнимых цейтинских формул на графе-экспандере. 

В данном докладе будут объяснены понятия цейтинских формул, свободных бинарных диаграмм решений (FBDD) и упорядоченных бинарных диаграмм решений (OBDD).