Mathematical Logic and Discrete Mathematics at PDMI

Четверг, 12 ноября, Zoom. Начало в 14:00.

Докладчик: А.С. Куликов (ПОМИ).

Тема: Жадная гипотеза для задачи о надстроке неверна.

Abstract

Задача о (кратчайшей общей) надстроке — классическая труднорешаемая задача, являющаяся, в частности, математической моделью задачи сборки генома. В ней на вход даётся множество строк и требуется найти самую короткую строку, содержащую их все как подстроки.

Уже почти сорок лет остаётся открытой так называемая жадная гипотеза. Она утверждает, что следующий (до безобразия простой) жадный алгоритм является 2-приближённым: пока строк больше двух, взять две из них с максимальным наложением и заменить на их склейку (в итоге останется одно строка, которая обязательно будет надстрокой исходного набора).

Мы представим новые нижние и верхние оценки на гарантию приближения жадного алгоритма. В частности, покажем, что жадная гипотеза неверна.