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

16

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ół.

ho.history-overview analysis-of-algorithms

— Rob Simmons
źródło

Idealnym przykładem jest mnożenie macierzy. Ostatnie ulepszenia są w rzeczywistości lepszymi analizami (Le Gall, Williams itp.).

— Lwins,

Lwins - podejrzewałem, że może tak być, ale przeglądanie niektórych artykułów sprawiło, że pomyślałem, że nieco różnią się zarówno algorytmem, jak i analizą. Być może będę musiał spojrzeć głębiej.

— Rob Simmons,

To pół-odpowiedź, ponieważ jest to słynna wiadomość z drugiej ręki: pracując nad określeniem automatów Buechi ( dl.acm.org/citation.cfm?id=1398627 ), Safra pierwotnie przeanalizował swoją konstrukcję, aby uzyskać potęgę kwadratową. Następnie, po spisaniu konstrukcji i z powodu pewnych nieporozumień, uzyskał lepszy (optymalny) wykładnik .

n \log n

$n\log n$

— Shaull

Sugerowałbym przyjrzenie się problemom z planowaniem ruchu - wydaje mi się, że było tam kilka przypadków. Również IIRC dokładna złożoność algorytmu (-ów?) Była przedmiotem badań przez dłuższy czas.

— Steven Stadnicki

1

Nieco inaczej, ale dowód na istnienie danych wejściowych spełniających klauzul w instancji 3SAT został ulepszony do jawnego algorytmu poprzez dokładniejszą analizę.

7 m / 8

$7m/8$

— Stella Biderman,

23

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).

— Peter Shor
źródło

2

Historia tej struktury danych jest dla mnie trochę niejasna i dobrze byłoby ją zbadać. Przejrzałem artykuł Gallera i Fischera i wydaje się, że opisuje on strukturę danych Disjoint Sets Forest (DSF), ale bez kluczowej heurystyki kompresji ścieżki (PC) i ważonej unii (WU). Hopcroft i Ullman przypisują DSF do PC i bez WU Tritterowi, powołując się na Knutha. Nie jestem pewien, czy DSF z PC i WU został zaproponowany w opublikowanym artykule przed tekstem Hopcroft i Ullmana, chociaż nie byłbym zaskoczony, gdyby tak było.

— Sasho Nikolov,

1

O (n \log \log n)

$O(n \log\log n)$

Θ (n)

$\Theta(n)$

O (n \log^{*} n)

$O(n \log^* n)$

— Peter Shor,

12

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

— Jan Johannsen
źródło

To naprawdę satysfakcjonująca odpowiedź! Myślę, że to i przykłady Unii Znajdź to najlepsze przykłady tego, na co liczyłem.

— Rob Simmons

8

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

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

L_{p} (v, c) = \exp ((c + o (1)) (\log p)^{v} (\log \log p)^{1 - v})

$L_p(v, c) = \exp((c+o(1))(\log p)^v (\log \log p)^{1-v})$

— znak
źródło

1

Bardzo w duchu, dziękuję!

— Rob Simmons,

6

$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$

— Klemens C.
źródło

4

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

— Chandra Chekuri
źródło

4

$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 )

— JimN
źródło

Dokonywanie nowych wyborów jest bliskie temu, czego szukałem, ale nie jest całkiem możliwe - w pewnym sensie bardziej szczegółowy algorytm jest „innym algorytmem” - ale wciąż są to bardzo ciekawe przykłady!

— Rob Simmons,