Dlaczego Chciwa Hipoteza jest tak trudna?

Niedawno dowiedziałem się o chciwych przypuszczeniach dotyczących najkrótszego problemu superstrun .

W tym problemie otrzymujemy zestaw ciągów $s_1,\dots, s_n$ i chcemy znaleźć najkrótszy superstrun $s$ tj. Taki, aby każdy $s_i$ pojawiał się jako podciąg $s$ .

Problem ten jest trudny do przeprowadzenia w NP i po długiej sekwencji dokumentów najbardziej znany algorytm aproksymacji dla tego problemu ma stosunek $2+\frac{11}{30}$ [Paluch '14].

W praktyce biolodzy używają następującego algorytmu Chciwości:

Na każdym kroku scal dwa ciągi, które mają maksymalne nakładanie się na wszystkie pary (maksymalny przyrostek, który jest prefiksem innego ciągu) i powtarzaj tę nową instancję, aż pozostanie tylko jeden ciąg (który jest superstrunem wszystkich ciągów wejściowych )

Niższa granica $2$ w stosunku przybliżenie tego Greedy algorytm może być uzyskane z wejścia $c(ab)^k,(ba)^k,(ab)^kc$ .

Co ciekawe, przypuszczono, że jest to najgorszy przykład, tj. Że Chciwy osiąga $2$ przybliżenie dla problemu najkrótszego superstrunu. Byłem bardzo zaskoczony, widząc, że tak naturalny i łatwy algorytm jest tak trudny do analizy.

Czy są jakieś intuicje, fakty, spostrzeżenia, przykłady sugerujące, dlaczego to pytanie jest tak trudne?

Pozwól mi najpierw spróbować podsumować to, co wiadomo na temat Chciwej hipotezy.

1. Blum, Jiang, Li, Tromp, Yannakakis dowodzą, że Chciwy Algorytm daje 4-przybliżenie, a Kaplan i Shafrir pokazują, że daje 3,5-przybliżenie dla problemu najkrótszego wspólnego superstrunu.
2. Wiadomo, że wersja chciwego algorytmu daje przybliżenie 3 ( Blum, Jiang, Li, Tromp, Yannakakis ).
3. $3$$4$
4. Chciwa hipoteza zachodzi, jeśli Chciwy Algorytm zdarza się łączyć ciągi w określonej kolejności ( Weinard, Schnitger ; Laube, Weinard ).
5. Algorytm zachłanności daje przybliżone 2- krotnie kompresję Tarhio, Ukkonen (która jest zdefiniowana jako całkowita długość łańcuchów wejściowych minus długość najkrótszego wspólnego superstrunu).
6. Istnieje niezwykle wydajna implementacja Greedy Al Algorytm Ukkonen .

Myślę, że jednym z powodów, dla których trudno jest udowodnić Chciwe Przypuszczenie, mogą być następujące. Większość podejść do udowodnienia gwarancji przybliżenia algorytmu zachłannego analizuje nakładający się wykres (lub równoważnie wykres przedrostka) wejściowego zestawu ciągów. Znamy tylko niektóre właściwości tych wykresów (takie jak Monge i Triple nierówności), ale właściwości te są niewystarczające do udowodnienia chciwej hipotezy ( Weinard, Schnitger ; Laube, Weinard ).