Жадная гипотеза для задачи о надстроке

Открытая лекция CS центра Лектор: Александр Куликов О лекции Задача о (кратчайшей общей) надстроке — классическая труднорешаемая задача, являющаяся, в частности, математической моделью задачи сборки генома. В ней на вход даётся множество строк и требуется найти самую короткую строку, содержащую их все как подстроки. На сегодняшний день мы не знаем эффективных точных алгоритмов для её решения. Наилучший известный приближённый алгоритм для этой задачи находит решение, которое гарантированно не более чем в 2