Почему жадная гипотеза так сложна?

Недавно я узнал о гипотезе Жадности о самой короткой проблеме суперструн .

В этой задаче нам дан набор строк и мы хотим найти самую короткую суперструну то есть такую, чтобы каждая как подстрока .$s_1,\dots, s_n$ $s$$s_i$$s$

Эта задача является NP-трудной, и после длинной серии работ наиболее известный алгоритм приближения для этой задачи имеет отношение [Paluch '14].$2+\frac{11}{30}$

На практике биологи используют следующий алгоритм Жадности:

На каждом шаге объединяйте две строки, которые имеют максимальное перекрытие по всем парам (максимальный суффикс, который является префиксом другой строки), и повторяйте для этого нового экземпляра, пока не останется только одна строка (которая является суперструной всех входных строк). )

Нижнюю границу в отношении аппроксимации этого алгоритма жадности можно получить из входных данных .$2$$c(ab)^k,(ba)^k,(ab)^kc$

Интересно, что это было предположено, что это худший пример, то есть, что Жадность достигает аппроксимации для самой короткой проблемы суперструн. Я был очень удивлен, увидев, что такой естественный и простой алгоритм так сложно анализировать.$2$

Есть ли интуиция, факты, наблюдения, примеры, которые указывают на то, почему этот вопрос так сложен?

Позвольте мне сначала попытаться обобщить то, что известно о гипотезе жадности.

1. Блум, Цзян, Ли, Тромп, Яннакакис доказывают, что алгоритм Жадности дает 4-аппроксимацию, а Каплан и Шафрир показывают, что он дает 3,5-аппроксимацию для самой короткой общей задачи суперструн.
2. Известно, что вариант жадного алгоритма дает 3-аппроксимацию ( Блюм, Цзян, Ли, Тромп, Яннакакис ).
3. Гипотеза жадности справедлива, когда все входные строки имеют всю длину не более ( Tarhio, Ukkonen ; Cazaux, Rivals ) или ( Kulikov, Savinov, Sluzhaev ).$3$$4$
4. Гипотеза жадности справедлива, если алгоритм жадности объединяет строки в каком-то определенном порядке ( Вейнард, Шнитгер ; Лаубе, Вейнард ).
5. Алгоритм Жадности дает 2-аппроксимацию сжатия Tarhio, Ukkonen (которая определяется как общая длина входных строк минус длина кратчайшего общего суперструнга).
6. Существует чрезвычайно эффективная реализация алгоритма Greedy Ukkonen .

Я думаю, что одной из причин, почему трудно доказать гипотезу Жадности, может быть следующее. Большинство подходов к доказательству гарантий аппроксимации алгоритма Жадности анализируют граф перекрытия (или, что то же самое, граф префикса) входного набора строк. Нам известны только некоторые свойства этих графов (такие как неравенства Монжа и Тройного), но эти свойства доказуемо недостаточны для доказательства гипотезы Жадности ( Вейнард, Шнитгер ; Лаубе, Вейнард ).