Superstring genau lösen

Was ist über die genaue Komplexität des kürzesten Superstring-Problems bekannt? Kann es schneller gelöst werden als ? Gibt es bekannte Algorithmen, die den kürzesten Superstring lösen, ohne ihn auf TSP zu reduzieren? $O^*(2^n)$

UPD: unterdrückt Polynomfaktoren. $O^*(\cdot)$

Das kürzeste Superstring-Problem ist ein Problem, dessen Antwort die kürzeste Zeichenfolge ist, die jede Zeichenfolge aus einem gegebenen Satz von Zeichenfolgen enthält. Die Frage ist nach der Optimierungserweiterung eines berühmten NP-harten Problems Shortest Superstring (Garey und Johnson, S.228).

cc.complexity-theory ds.algorithms graph-theory tsp exp-time-algorithms Alex Golovnev
quelle

Was ist "das Superstring-Problem"?

Jeffs

Ich meinte das kürzeste Superstring-Problem, ich habe es behoben. Vielen Dank!

Alex Golovnev

Okay, was ist dann "das kürzeste Superstring-Problem"? Ich kann mir einige Probleme vorstellen, die diesen Namen verdienen, und einige weitere, die "das kürzeste Supersequenzproblem " genannt werden sollten, aber wahrscheinlich nicht in der Praxis sind. Geben Sie uns bitte einen Kontext!

Jeffs

Was ist dein Problembereich? Wenn Sie beispielsweise nach der kürzesten Super-Zeichenfolge für die Genomfragmentierung suchen, weil die Genomfragmentierung Diagramme mit begrenzter Baumbreite erstellt, können Sie einen schnellen Algorithmus verwenden. Wenn Sie jedoch nur an schnelleren als den verfügbaren Algorithmen interessiert sind, lautet Ihre Antwort Nein, es sei denn, Sie können einen schnelleren Algorithmus verwenden In TSP (wegen einfacher Reduktion) gibt es auch einen Algorithmus in lokal begrenzten Baumbreitengraphen.

O^{*} (2^{\sqrt{n}})

$O^*(2^{\sqrt n})$

Saeed

@AlexGolovnev, Ja, Sie haben Recht, dies ist ATSP, aber für begrenzte Baumbreite finde ich es gut, cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 zu sehen, oder wenn Sie mehr über sie wissen möchten, ist es auch gut, algorithmisch

Saeed

Antworten:

Angenommen, die Zeichenfolgen haben ein Längenpolynom in , dann gibt es mindestens eine Zeitlösung. Der Grund ist die bekannte Reduktion vom kürzesten gemeinsamen Superstring-Problem auf ATSP mit polynomgroßen Ganzzahlgewichten, die Sie wiederum durch Polynominterpolation lösen können, wenn Sie Hamilton-Zyklen in einem gerichteten Multigraph zählen können. Das letztere Problem hat eine Zeitlösung. Björklund 2012 $n$ $2^{n-\Omega(\sqrt{n/\log n})}$ $2^{n-\Omega(\sqrt{n/\log n})}$

Die Reduktion von ATSP mit Gewichten für jedes Paar von Eckpunkten auf die Hamiltonsche Zykluszählung lautet wie folgt: $w_{uv}$ $u,v$

Für , wobei eine Obergrenze für alle Summen von Gewichten in der ATSP-Instanz ist, erstellen Sie einen Graphen in dem Sie jedes Gewicht ersetzen. mit Bögen von nach . $r=1,2,\cdots,w_\mbox{sum}$ $w_\mbox{sum}$ $n$ $G_r$ $w_{uv}$ $r^{w_{uv}}$ $u$ $v$

Durch Lösen der Hamiltonschen für jedes können Sie durch Polynominterpolation ein Polynom mit , das der Anzahl der TSP-Touren im Originalgraphen entspricht Gewicht . Daher löst das Lokalisieren des kleinsten so dass nicht Null ist, das Problem. $G_r$ $\sum_{l=0}^{w_\mbox{sum}} a_lr^l$ $a_l$ $l$ $l$ $a_l$

Andreas Björklund
quelle

Vielen Dank! Ich kannte diesen Zusammenhang mit der Hamilton-Zählung nicht.

Alex Golovnev

@AlexGolovnev: Aber die Reduktion ist mehr oder weniger die gleiche wie zB bei dem Ergebnis von Kohn, Gottlieb, Kohn, das Sie in Ihrer eigenen Antwort zitiert haben? Es ist eine einfache Einbettung des Min-Summen-Semirings in die ganzen Zahlen. Wie auch immer, danke, dass Sie mir klar gemacht haben, dass die nächste Version meines Papiers dies explizit angeben sollte.

Andreas Björklund

Ich habe das Problem untersucht und einige Ergebnisse gefunden. Der kürzeste gemeinsame Superstring (SCS) kann in Zeit mit nur polynomialem Raum gelöst werden ( Kohn, Gottlieb, Kohn ; Karp ; Bax, Franklin ). $2^n$

Die bekannteste Näherung ist (Paluch). $2\frac{11}{30}$

Die bekannteste Annäherung an die Komprimierung ist (Paluch). $3\over4$

Wenn SCS durch einen Faktor über dem binären Alphabet angenähert werden kann, kann es durch einen Faktor über einem beliebigen Alphabet angenähert werden ( Vassilevska-Williams ). $\alpha$ $\alpha$

SCS kann nicht mit einem Verhältnis besser als sei denn, P = NP ( Karpinski, Schmied ). $1.0029$

Die maximale Kompression kann nicht mit einem Verhältnis besser als sei denn, P = NP ( Karpinski, Schmied ). $1.0048$

Für Ergänzungen und Anregungen wäre ich dankbar.

Alex Golovnev
quelle

Hier ist das kürzeste Superstring-Problem: Sie erhalten Strings über einem Alphabet und möchten den kürzesten String über , der jedes als Folge aufeinanderfolgender Zeichen enthält, dh einen Teilstring. $n$ $s_1,\ldots, s_n$ $\Sigma$ $\Sigma$ $s_i$

Wenn wir über genaue Algorithmen für das Problem sprechen, entspricht das Ermitteln der Länge der kürzesten Superzeichenfolge dem Ermitteln der maximalen Komprimierung die die Summe aller aufeinanderfolgenden Zeichenfolgenüberlappungen in der letzten Superzeichenfolge ist, dh . $L$ $C$ $C=\sum_i |s_i|-L$

Soweit ich weiß, läuft der schnellste exakte Algorithmus für den kürzesten Superstring in ( ), wobei die Anzahl der Strings ist. Dies ist ein einfacher dynamischer Programmieralgorithmus, der dem dynamischen Programmieralgorithmus für den längsten Pfad (und andere Probleme) ähnelt: $O^*$ $2^n$ $n$

Für jede Teilmenge der Zeichenfolgen und der Zeichenfolge in berechnen wir die maximale Komprimierung für alle Superzeichenfolgen über wobei die erste Zeichenfolge ist, die in der Superzeichenfolge erscheint, und speichern diese als C (( )). Wir tun dies, indem wir zuerst alle Teilmengen mit nur einem Element verarbeiten und dann die C (( )) - Werte für Teilmengen auf Zeichenfolgen aus denen auf Zeichenfolgen aufbauen . Speziell: $S$ $v$ $S$ $S$ $v$ $v,S$ $v,S$ $S$ $k$ $k-1$

$u$ $S'$ $k-1$ $u$ $u,{u}\cup S'$ $v$ $S'$ $u$ $v$ $v,S'$

$n^2 2^n + n^2 l$ $l$

$l$ $2^n$

virgi
quelle

O^{*} (2^{n})

$O^*(2^n)$

Wie gesagt, ich glaube nicht, dass eine schnellere Lösung bekannt ist.

Virgi

O^{*} (2^{n})

$O^*(2^n)$