Kiedy znaleźliśmy lepsze granice dla znanych algorytmów?

Czy istnieją interesujące przypadki algorytmów, które zostały opublikowane ze sprawdzonymi granicami i gdzie opublikowano później ściśle lepsze ograniczenia? Nie lepsze algorytmy z lepszymi granicami - oczywiście tak się stało! Ale lepsza analiza prowadząca do lepszego powiązania z istniejącym algorytmem

Myślałem, że mnożenie macierzy jest tego przykładem, ale sam sobie z tego poradziłem (być może niepoprawnie!) Po tym, jak starałem się lepiej zrozumieć Coppersmith – Winograd i jego przyjaciół.

Algorytm Związek zdobycia, które Tarjan ¹ wykazywały miał złożoność $n \alpha(n)$ , gdzie $\alpha(n)$ jest odwrotnością funkcji Ackermann, były analizowane uprzednio przez kilka osób. Według Wikipedii został wymyślony przez Gallera i Fischera ² , ale wydaje się to niepoprawne, ponieważ nie mieli wszystkich elementów algorytmu potrzebnych do szybkiego uruchomienia.

Na podstawie krótkich skanów dokumentów wydaje się, że algorytm został wymyślony przez Hopcroft i Ullman ³ , którzy wyznaczyli (niepoprawne) ograniczenie czasowe $O(n)$ . Fischer ⁴ następnie znalazł błąd w dowodzie i wyznaczył limit czasu $O(n \log\log n)$ . Następnie Hopcroft i Ullman ⁵ wyznaczyli limit czasu $O(n \log ^*n)$ , po czym Tarjan ¹ znalazł limit czasu (optymalny) $O(n \alpha(n))$ .

¹ RE Tarjan, „Skuteczność dobrego, ale nie liniowego algorytmu unii zbioru” (1975).
² BS Galler i MJ Fischer, „Ulepszony algorytm równoważności” (1964).
³ JE Hopcroft i JD Ullman, „Algorytm łączenia listy liniowej” (1971).
⁴ MJ Fischer, „Efektywność algorytmów równoważności” (1972).
⁵ JE Hopcroft i JD Ullman, „Algorytmy łączenia zestawów” (1973).

$k\text{-} \mathrm{SAT}$$O(1.364^n)$$3\text{-}\mathrm{SAT}$$O(1.308^n)$$3\text{-}\mathrm{SAT}$ znany wtedy.

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

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

$k$$O(n^{k+o(1)})$$O(n^{2k-2})$$O(n^{1.98k+O(1)})$

$\Omega(n^k)$

Uwaga: Przemówienie Jasona Li (i odpowiednie slajdy) można znaleźć na stronie internetowej TCS + .

$k$

$k$$(2k-1)$$k$

$3$ dać bardziej dopracowaną analizę (liczenie podproblemów / podstruktur), co prowadzi do lepszych powtórzeń i lepszych czasów działania. Wydaje mi się, że w sparametryzowanej literaturze złożonej jest wiele takich przykładów, w których dodanie kolejnej zmiennej do analizy może prowadzić do poprawy czasu działania, ale nie jestem w tej grze od kilku lat i nie mogę wymyślić konkretnych chwila. Istnieje wiele artykułów w obszarach FPT i PTAS, które pojawiają się, gdy szukamy „ulepszonej analizy” w tytułach artykułów.

Jeśli określenie opcji liczy się jako ten sam algorytm (jak heurystyka głębokości rangi znalezienia związku), to algorytm Edmondsa-Karpa jest „ulepszoną analizą” Forda-Fulkersona i wyobrażam sobie, że istnieje wiele innych problemów z algorytmami które zauważyły ​​ulepszenia w czasie wykonywania dzięki nowym regułom wyboru.

Potem jest cała masa zamortyzowanej analizy istniejących algorytmów (myślę, że union-find pasuje do tego opisu, oto kolejny https://link.springer.com/article/10.1007/s00453-004-1145-7 )