Submitted by kulikov on 13 Aug 2012, Mon, 14:03
Дата:
17 Aug 2012, Fri, 11:30
Докладчик:
Иван Михайлин
Задача о кратчайшей надстроке (shortest common superstring problem, SCS) -- классическая NP-трудная задача, практические применения которой включают сборку генома, хранение и сжатие данных. Лучшим известным приближением для данной задачи является 2.5-приближение (Свидик, 2005), лучшей верхней оценкой на время работы точного алгоритма -- 2^n, где n -- это количество входных строк (Хелд, Карп, 1962).
В докладе будет рассказано об улучшении данных оценок для NP-трудного частного случая задачи, где все входные строки имеют длину 3. Именно, будет представлено 4/3-приближение, а также точный алгоритм со временем работы 3^{n/3}. В основе обоих алгоритмов лежат графы де Брюйна и задача о деревенском почтальоне (rural postman problem).