22.09.2015 О жадном алгоритме для задачи о кратчайшей надстроке (Иван Толстоганов)

Существует гипотеза о том, что жадный алгоритм для задачи о надстроке является 2-приближенным (на текущий момент лучшим является $2^{\frac{11}{30}}$ - приближение). В докладе будет рассмотрено доказательство этой гипотезы для некоторого подмножества входов.