Warum ist die gierige Vermutung so schwierig?

14

Ich habe kürzlich von der gierigen Vermutung für das kürzeste Superstring-Problem erfahren .

In diesem Problem erhalten wir eine Menge von Strings und wollen den kürzesten Superstring dh so, dass jeder als ein Teilstring von .s1,,sn ssichs

Dieses Problem ist NP-hart und nach einer langen Abfolge von Arbeiten hat der bekannteste Näherungsalgorithmus für dieses Problem ein Verhältnis von [Paluch '14].2+1130

In der Praxis verwenden Biologen den folgenden Greedy-Algorithmus:

Führen Sie bei jedem Schritt zwei Zeichenfolgen zusammen, die sich über alle Paare maximal überlappen (das maximale Suffix, das dem Präfix einer anderen Zeichenfolge entspricht), und wiederholen Sie diese neue Instanz, bis nur noch eine Zeichenfolge übrig ist (die eine Superzeichenfolge aller Eingabezeichenfolgen ist) )

Eine untere Grenze von im Näherungsverhältnis dieses Greedy-Algorithmus kann aus der Eingabe .2c(einb)k,(bein)k,(einb)kc

Interessanterweise wurde vermutet, dass dies das schlechteste Beispiel ist, dh, dass Greedy eine Approximation für das kürzeste Superstring-Problem erreicht. Ich war sehr überrascht zu sehen, dass ein so natürlicher und einfacher Algorithmus so schwer zu analysieren ist.2

Gibt es irgendwelche Anschauungen, Fakten, Beobachtungen, Beispiele, die nahelegen, warum diese Frage so herausfordernd ist?

Mathieu Mari
quelle
7
Einer der Gründe könnte sein, dass die bekannten Eigenschaften der Standardgrafendarstellungen des Problems (wie die Ungleichungen von Monge und Triple) nachweislich nicht ausreichen, um die gierige Vermutung zu beweisen. Siehe zB Laube, Weinard "Bedingte Ungleichungen und das kürzeste gemeinsame Superstring-Problem" und Weinard, Schnitger "Über die gierige Superstring-Vermutung".
Alex Golovnev
@ AlexGolovnev: Scheint mir eine perfekte Antwort zu sein!
Joshua Grochow
@ JoshuaGrochow: Danke! Ich werde es jetzt auf eine Antwort erweitern.
Alex Golovnev

Antworten:

8

Lassen Sie mich zunächst zusammenfassen, was über die Gierige Vermutung bekannt ist.

  1. Blum, Jiang, Li, Tromp, Yannakakis beweisen, dass der Greedy-Algorithmus eine 4-Approximation liefert, und Kaplan und Shafrir zeigen, dass er eine 3,5-Approximation für das Problem der kürzesten gemeinsamen Superstrings liefert.
  2. Es ist bekannt, dass eine Version des Greedy-Algorithmus eine 3-Approximation liefert ( Blum, Jiang, Li, Tromp, Yannakakis ).
  3. 34
  4. Die Greedy-Vermutung gilt, wenn der Greedy-Algorithmus Strings in einer bestimmten Reihenfolge zusammenführt ( Weinard, Schnitger ; Laube, Weinard ).
  5. Der Greedy-Algorithmus liefert eine 2-Approximation der Komprimierung Tarhio, Ukkonen (definiert als die Gesamtlänge der Eingabe-Strings abzüglich der Länge des kürzesten gemeinsamen Superstrings).
  6. Es gibt eine äußerst effiziente Implementierung des Greedy-Algorithmus Ukkonen .

Ich denke, einer der Gründe, warum es schwierig ist, die gierige Vermutung zu beweisen, könnte folgender sein. Die meisten Ansätze zum Nachweisen von Approximationsgarantien des Greedy-Algorithmus analysieren den Überlappungsgraphen (oder äquivalent den Präfixgraphen) des Eingabesatzes von Zeichenfolgen. Wir kennen nur einige Eigenschaften dieser Graphen (wie Monge- und Triple-Ungleichungen), aber diese Eigenschaften reichen nachweislich nicht aus, um die Gierige Vermutung zu beweisen ( Weinard, Schnitger ; Laube, Weinard ).

Alex Golovnev
quelle