Komplexität der Faltung im Max / Plus-Ring

10

Wir können Faltung in O(nlogn) für Plus / Multiplikations-Polynome mit FFT durchführen. Der Ansatz scheint jedoch für Ringe im Allgemeinen nicht sehr verallgemeinerbar zu sein. Hat es Fortschritte bei der naiven O(n2) -Faltung für den Max / Plus-Ring gegeben?

soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)max(x,y))

Thomas Ahle
quelle
1
@ChaoXu Kommentar -> Antwort?
Sasho Nikolov

Antworten:

11

Es gibt eine allgemeinere Frage zum Mathoverflow .

Ich habe eine ähnliche Frage zu CS.SE gestellt . jbapple gab eine gute Antwort. Zitieren

"Halsketten, Faltungen und X + Y", Von Bremner et al. zeigt einen -Algorithmus für dieses Problem im realen RAM und einen Algorithmus im ungleichmäßigen linearen Entscheidungsbaummodell.O(n2(lglgn)3lg2n)O(nn)

Jede Verbesserung dieser Grenze wirft ein Licht auf einige schwierige offene Probleme wie das Sortieren von und den kürzesten Weg aller Paare.X+Y

Wenn eine der Funktionen konvex / konkav ist, können wir das Problem in lösen . Siehe "Beschleunigung der dynamischen Programmierung", von Eppstein et al. .O(nlogn)

Chao Xu
quelle
1
Vielen Dank. Ich habe es auch genossen, darüber auf dem Mathoverflow-Link zu lesen.
Thomas Ahle
Ich frage mich, ob "monoton ansteigend" eine nützliche Eigenschaft sein könnte.
Thomas Ahle
2
Das erste Problem, das die Autoren im Necklaces-Papier zu lösen versuchen, nimmt monoton zu. Es ist wahrscheinlich, dass kein Algorithmus bekannt ist, der eine bessere Leistung als der allgemeine Fall erbringt.
Chao Xu