Wann haben wir bessere Grenzen für bekannte Algorithmen gefunden?

16

Gibt es interessante Fälle von Algorithmen, die mit nachgewiesenen Grenzen veröffentlicht wurden und in denen später streng bessere Grenzen veröffentlicht wurden? Keine besseren Algorithmen mit besseren Grenzen - das ist offensichtlich passiert! Eine bessere Analyse führt jedoch zu einer besseren Bindung an einen vorhandenen Algorithmus

Ich dachte, die Matrixmultiplikation sei ein Beispiel dafür, aber ich habe mich (vielleicht falsch!) Dagegen ausgesprochen, nachdem ich versucht hatte, Kupferschmied-Winograd und seine Freunde besser zu verstehen.

Rob Simmons
quelle
Ein ideales Beispiel ist die Matrixmultiplikation. Jüngste Verbesserungen sind in der Tat alle bessere Analysen (Le Gall, Williams usw.).
Lwins
Lwins - Ich vermutete, dass dies der Fall sein könnte, aber das Überfliegen einiger Artikel ließ mich glauben, dass sie sowohl den Algorithmus als auch die Analyse geringfügig veränderten. Ich muss vielleicht tiefer schauen.
Rob Simmons
Dies ist eine halbe Antwort, da es sich um ein Hörensagen aus zweiter Hand handelt: Bei der Bestimmung von Buechi-Automaten ( dl.acm.org/citation.cfm?id=1398627 ) analysierte Safra ursprünglich seine Konstruktion, um einen quadratischen Exponenten zu haben. Dann, nachdem er die Konstruktion aufgeschrieben hatte und aufgrund von Missverständnissen, endete er mit dem besseren (optimalen) Exponenten. nLogn
Shaull
Ich würde vorschlagen, Bewegungsplanungsprobleme zu untersuchen - ich habe das Gefühl, dass es dort mehrere Fälle gab. Auch die genaue Komplexität des Simplex-Algorithmus (s?) War im IIRC lange Zeit Gegenstand von Untersuchungen.
Steven Stadnicki
1
Etwas anders, aber der Existenznachweis einer Eingabe, die der Klauseln in einer 3SAT-Instanz erfüllt, wurde durch genauere Analyse zu einem expliziten Algorithmus verbessert. 7m/8
Stella Biderman

Antworten:

23

Der Union-Find-Algorithmus, den Tarjan 1 zeigte, hatte die Komplexität nα(n) , wobei α(n) die inverse Ackermann-Funktion ist, wurde zuvor von mehreren Personen analysiert. Laut Wikipedia wurde es von Galler und Fischer 2 erfunden , aber das scheint falsch zu sein, da sie nicht alle Komponenten des Algorithmus hatten, die nötig waren, um es so schnell laufen zu lassen.

Basierend auf kurzen Scans der Arbeiten scheint es, dass der Algorithmus von Hopcroft und Ullman 3 erfunden wurde , die eine (falsche) Ö(n) -Zeitgrenze angegeben haben. Fischer 4 fand dann den Fehler im Beweis und gab eine Ö(nLogLogn) -Zeitbegrenzung. Als nächstes gaben Hopcroft und Ullman 5 eine Ö(nLogn) -Zeitgrenze an, wonach Tarjan 1 die (optimale) Ö(nα(n)) -Zeitgrenze fand.

1 RE Tarjan, "Effizienz eines guten, aber nicht linearen Mengenvereinigungsalgorithmus" (1975).
2 BS Galler und MJ Fischer, "Ein verbesserter Äquivalenzalgorithmus" (1964).
3 JE Hopcroft und JD Ullman, "Ein linearer Algorithmus zum Zusammenführen von Listen" (1971).
4 MJ Fischer, "Effizienz von Äquivalenzalgorithmen" (1972).
5 JE Hopcroft und JD Ullman, "Set-merging algorithms" (1973).

Peter Shor
quelle
2
Die Geschichte dieser Datenstruktur ist mir etwas unklar und es wäre schön, sie zu untersuchen. Ich habe den Artikel von Galler und Fischer überflogen, und er scheint die Datenstruktur von Disjoint Sets Forest (DSF) zu beschreiben, jedoch ohne die Heuristiken für die Komprimierung des entscheidenden Pfads (PC) und die gewichtete Vereinigung (WU). Hopcroft und Ullman schreiben Tritter DSF mit PC und ohne WU unter Berufung auf Knuth zu. Ich bin nicht sicher, ob DSF mit PC und WU in einem veröffentlichten Artikel vor Hopcroft und Ullmans Artikel vorgeschlagen wurde, obwohl ich mich nicht wundern würde, wenn dies der Fall wäre.
Sasho Nikolov
1
@Sasho: Dies sollte alles überprüft werden, da es auf kurzen Scans der Papiere basiert. Tarjan schreibt Michael Fischer in "Efficiency of Equivalence Algorithms" (1972) DSF mit PC und WU zu, womit eine Laufzeit von wird. Fischers Papier scannen, er scheint den Algorithmus zu Hopcroft und Ullman in „Eine lineare Liste verschmelzenden Algorithmus“ zuzuschreiben, aber sie geben einen Θ ( n ) Laufzeit für sie, den Beweis von denen Fischer zeigt nicht korrekt ist. Laut Tarjan lösen sich Hopcroft und Ullman in "Set-merging algorithms" durch die Angabe einer O ( n log n ) -Bindung.Ö(nLogLogn)Θ(n)Ö(nLogn)
Peter Shor
12

Es war bekannt, dass der Algorithmus von Paturi, Pudlák, Saks und Zane (PPSZ) für k-SEINT eine Laufzeit von Ö(1,364n) für 3-SAT mit einer besseren Grenze von O(1.308n) für Formeln, die garantiert eine eindeutige befriedigende Zuordnung haben. Später gab Hertli eine verbesserte Analyse ab, aus der hervorgeht, dass diese verbesserte Laufzeitbindung auch für den allgemeinen Fall gilt, sodass PPSZ der beste Algorithmus für 3-SAT zu der Zeit bekannt.

Jan Johannsen
quelle
Das ist eine wirklich befriedigende Antwort! Ich denke, es und die Beispiele von Union Find sind die besten Beispiele für das, was ich mir erhofft habe.
Rob Simmons
8

Der Logjam-Angriff erwähnt, dass die Analyse des allgemeinen Zahlenfeldsiebs (angewendet auf die Berechnung diskreter Logarithmen über Fp ) für den Abstiegsschritt eng gesteckt war (siehe oben links auf der 3. Seite). Da dies der einzige Schritt ist, der nicht vorausberechnet werden kann (wenn Fp festgelegt ist), war seine Effizienz maßgeblich für ihren Angriff.

Lp(1/3,32/3)Lp(1/3,1.232)

Lp(v,c)=exp((c+Ö(1))(Logp)v(LogLogp)1-v)

Kennzeichen
quelle
1
Sehr im Geiste, danke!
Rob Simmons
5

kÖ(nk+Ö(1))Ö(n2k-2)Ö(n1,98k+Ö(1))

Ω(nk)

Hinweis: Ein Vortrag von Jason Li (und die entsprechenden Folien) finden Sie auf der TCS + Website .


k optimal cut , Anupam Gupta, Euiwoong Lee und Jason Li. arXiv: 1911 , 09165 , 2019.

Clement C.
quelle
4

k(2k-1)-kompetitiv von Koutsipias und Papadimitrou - der Algorithmus war bisher bekannt und wurde nur in Sonderfällen analysiert. Es wird vermutet zu seink-Wettbewerbsfähig.

Chandra Chekuri
quelle
4

Das 3-Hitting Set Problem hatte ein paar Iterationen der "besseren Analyse" (siehe Fernau's Papers [1] [2] ) Der Algorithmus vor diesem Papier hatte einige willkürliche Auswahlmöglichkeiten (wie "Wähle eine Kante" ...), aber wenn die Auswahlmöglichkeiten sind In gewisser Weise speziell ausgewählt, ermöglicht es eine verfeinerte Analyse, bei der die Verbesserung eintritt. Und ich denke, seine Anhänge in 1Geben Sie eine genauere Analyse (Zählen von Teilproblemen / Teilstrukturen), die zu besseren Wiederholungen und damit zu besseren Laufzeiten führt. Ich denke, es gibt eine Reihe solcher Beispiele in der Literatur zu parametrisierten Komplexitäten, bei denen das Hinzufügen einer weiteren Variablen zur Analyse zu verbesserten Laufzeiten führen kann. Ich bin jedoch seit einigen Jahren nicht mehr in diesem Spiel und kann mir keine spezifischen Beispiele vorstellen der Moment. Es gibt eine Reihe von Artikeln in FPT- und PTAS-Bereichen, die bei der Suche nach "verbesserten Analysen" in den Papiertiteln auftauchen.

Wenn das Angeben von Auswahlen als derselbe Algorithmus gilt (wie die Tiefenrang-Heuristik von Union-Find), dann ist der Edmonds-Karp-Algorithmus eine 'verbesserte Analyse' von Ford-Fulkerson, und ich würde mir vorstellen, dass es viele andere Probleme gibt, bei denen Algorithmen auftreten das hat Laufzeitverbesserungen von neuen Auswahlregeln gesehen.

Dann gibt es eine ganze Reihe von amortisierten Analysen bestehender Algorithmen (ich denke, Union-Find passt unter diese Beschreibung, hier ist eine andere https://link.springer.com/article/10.1007/s00453-004-1145-7 )

JimN
quelle
Neue Entscheidungen zu treffen fühlt sich an wie das, wonach ich gesucht habe, ist aber nicht ganz da - in gewissem Sinne ist ein spezifizierterer Algorithmus ein "anderer Algorithmus" - aber dies sind immer noch sehr interessante Beispiele!
Rob Simmons