Quand avons-nous trouvé de meilleures limites pour les algorithmes connus?

Existe-t-il des exemples intéressants d'algorithmes qui ont été publiés avec des limites prouvées et où des limites strictement meilleures ont été publiées par la suite? Pas de meilleurs algorithmes avec de meilleures limites - c'est évidemment ce qui est arrivé! Mais une meilleure analyse conduisant à une meilleure limite sur un algorithme existant

Je pensais que la multiplication matricielle en était un exemple, mais je m'en suis dissocié (peut-être à tort!) Après avoir essayé de mieux comprendre Coppersmith – Winograd et ses amis.

L' algorithme Union-Find, dont Tarjan ^{1 a} montré la complexité $n \alpha(n)$ , où $\alpha(n)$ est la fonction Ackermann inverse, avait été analysé précédemment par plusieurs personnes. Selon Wikipedia, il a été inventé par Galler et Fischer ² , mais cela semble être incorrect, car ils n'avaient pas tous les composants de l'algorithme nécessaires pour le faire fonctionner aussi rapidement.

Sur la base de brèves analyses des articles, il semble que l'algorithme a été inventé par Hopcroft et Ullman ³ , qui ont donné une limite de temps $O(n)$ (incorrecte) . Fischer ^{4 a} ensuite trouvé l'erreur dans la preuve et a donné une limite de temps $O(n \log\log n)$ . Ensuite, Hopcroft et Ullman ^{5 ont} donné une limite de temps $O(n \log ^*n)$ , après quoi Tarjan ^{1 a} trouvé la limite de temps (optimale) $O(n \alpha(n))$ .

¹ RE Tarjan, "Efficacité d'un bon algorithme d'union d'ensemble non linéaire" (1975).
² BS Galler et MJ Fischer, "Un algorithme d'équivalence amélioré" (1964).
³ JE Hopcroft et JD Ullman, «Un algorithme de fusion de liste linéaire» (1971).
⁴ MJ Fischer, "Efficacité des algorithmes d'équivalence" (1972).
⁵ JE Hopcroft et JD Ullman, «Set-merging algorithms» (1973).

L'algorithme de Paturi, Pudlák, Saks et Zane (PPSZ) pour $k\text{-} \mathrm{SAT}$ était connu pour avoir un temps de fonctionnement de $O(1.364^n)$ pour $3\text{-}\mathrm{SAT}$ , avec une meilleure limite de $O(1.308^n)$ pour les formules garanties d'avoir une affectation satisfaisante unique. Plus tard, Hertli a donné une analyse améliorée montrant que cette limite d'exécution améliorée vaut également pour le cas général, montrant ainsi PPSZ comme le meilleur algorithme pour $3\text{-}\mathrm{SAT}$ connu à l'époque.

$\mathbb{F}_p$$\mathbb{F}_p$

$L_p(1/3, 3^{2/3})$$L_p(1/3, 1.232)$, where:

Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm for the minimum $k$-cut problem has, in fact, asymptotic time complexity $O(n^{k+o(1)})$, improving on the original analysis which gave $O(n^{2k-2})$ (and on previous work by the same authors, which obtained a different algorithm running in time $O(n^{1.98k+O(1)})$).

This is likely to be (near)optimal, based on a conditional lower bound of $\Omega(n^k)$.

Note: A talk by Jason Li (and the corresponding slides) can be found on the TCS+ website.

[1] The Karger—Stein Algorithm is Optimal for $k$-cut, Anupam Gupta, Euiwoong Lee, Jason Li. arXiv:1911.09165, 2019.

The work function algorithm for $k$-server was shown to be $(2k-1)$-competitive by Koutsipias and Papadimitrou - the algorithm was known previously and analyzed only in special cases. It is conjectured to be $k$-competitive.

The $3$-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers [1] [2]) The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the choices are specifically-chosen in a certain way, it allows for a more refined analysis, that is where the improvement comes in. And I think his Appendices in 1 give a more refined analysis (counting subproblems/substructures) leading to better recurrences and so better runtimes. I think there are a number of such examples in the parameterized complexity literature, where adding another variable to the analysis can lead to improved runtimes, but I have been out of that game for several years now and I can't think of specific ones at the moment. There are a number of papers in FPT and PTAS areas that come up when looking for "improved analysis" in the paper titles.

If specifying choices counts as the same algorithm (like union-find's depth-rank heuristic), then the Edmonds-Karp algorithm is an 'improved analysis' of Ford-Fulkerson, and I'd imagine there are plenty of other problems that have algorithms that have seen runtime improvements from new choice rules.

Then there are a whole bunch of amortized analysis of existing algorithms (I think union-find fits under this description, here is another one https://link.springer.com/article/10.1007/s00453-004-1145-7 )