Czy znasz rozsądne algorytmy działające w czasie wielomianowym w (Długość wejściowa + Długość wyjściowa), ale których asymptotyczny czas działania w tej samej mierze ma naprawdę ogromny wykładnik / stałą (przynajmniej tam, gdzie jest udowodniona górna granica czasu działania taka droga)?
ds.algorithms
big-list
Joris
źródło
źródło
Odpowiedzi:
Algorytmy oparte na lemacie regularności są dobrym przykładem algorytmów wielomianowych ze straszliwymi stałymi (zarówno w wykładniku wykładniczym, jak i jako wiodące współczynniki).
Lemat o regularności Szemeredi mówi ci, że na dowolnym wykresie wierzchołków możesz podzielić wierzchołki na zestawy, w których krawędzie między parami zbiorów są „pseudolosowe” (tj. Gęstości wystarczająco dużych podzbiorów wyglądają jak gęstości na losowym wykresie) . Jest to struktura, z którą bardzo miło jest pracować, w związku z czym istnieją algorytmy korzystające z partycji. Chodzi o to, że liczba zestawów w partycji jest wykładniczą wieżą w parametrze pseudolosowości (patrz tutaj: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma ).n
Niektóre linki do algorytmów opartych na lemacie regularności, patrz np .: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf
źródło
Wiadomości z SODA 2013 : problem Max-Bisection można zbliżyć do współczynnika 0,8776 w czasie .O(n10100)
źródło
Oto dwa zrzuty ekranu z podejścia opartego na energii do rozwijania powiązań autorstwa Jasona H. Cantarelli, Erika D. Demaine, Hayley N. Iben, Jamesa F. O'Briena, SOCG 2004:
źródło
Oto najnowszy wynik z papierowej łamigłówki FUN 2012 autorstwa Erika D. Demaine'a, Martina L. Demaine'a, Yaira N. Minsky'ego, Josepha SB Mitchella, Ronalda L. Rivesta i Mihai Patrascu.
Nie daj się zwieść „wielomianowi” ... okazuje się, że to .O ( n43737)
źródło
Istnieje klasa problemów, których rozwiązania są trudne do obliczenia, ale zbliżać je do dowolnej dokładności jest łatwe , w tym sensie, że istnieje wielomian czasie algorytmy, które mogą zbliżyć się do rozwiązania w ciągu dla dowolnej stałej ε> 0. Istnieje jednak pewien haczyk: czas działania aproksymatorów może bardzo źle zależeć od 1 / ,, np. Być O ( n 1 / ϵ ) .( 1 + ϵ ) 1 / ϵ O ( n1 / ϵ)
Zobacz więcej informacji tutaj: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .
źródło
Chociaż czas działania takich algorytmów został następnie poprawiony, pierwotny algorytm próbkowania punktu z wypukłego ciała miał czas pracy .O~( n19)
Dyer, Frieze i Kannan: http://portal.acm.org/citation.cfm?id=102783
źródło
Jeśli jest tabelaryczną modalną lub superintuicyjną logiką, wówczas rozszerzone systemy Frege i podstawienia Frege proof dla L są wielomianowo równoważne, a wielomianowo wiernie interpretowalne w klasycznej EF (to jest twierdzenie 5.10 w moim artykule ). Wykładnik c symulacji wielomianowych nie jest wyraźnie określony w Twierdzeniu 5.10, ale dowód indukcyjny twierdzenia daje c = 2 O ( | F | ) , gdzie F jest skończoną ramką Kripkego, która generuje L , więc może być tak ogromna jak chcesz w zależności od logiki. (Gorzej w twierdzeniu 5.20.)L. L. do c = 2O ( | F| ) fa L.
źródło
Obecnie najbardziej znany algorytm rozpoznawania grafów map (uogólnienie grafów płaskich) działa . Thorup, Mapa wykresów w czasie wielomianowym.n120
Obliczenie równowagi na rynku Arrow-Debreu wymaga obliczeń maksymalnego przepływu , gdzie U jest maksymalną użytecznością. Duan, Mehlhorn, kombinatoryczny algorytm wielomianowy dla rynku liniowego Arrow-Debreu.O ( n6log( n U) ) U
źródło
Problem przemijalności piaskowca
Rozważ następujący proces. Weź grubą płytkę i upuść na nią cząsteczki piasku po jednym ziarnie na raz. Stos stopniowo narasta, a następnie duża część piasku zsuwa się z krawędzi płytki. Jeśli nadal będziemy dodawać cząsteczki piasku, po pewnym czasie konfiguracja hałdy zostanie powtórzona. Następnie konfiguracja staje się cykliczna, tzn. Ciągle powraca do stanu widocznego wcześniej.
Rozważ następujący model powyższego procesu. Modeluj kafelek jako siatkę . Cząsteczki piasku są upuszczane na wierzchołki tej siatki. Jeśli liczba cząstek w wierzchołku przekracza swój stopień, wówczas wierzchołek zapada się, a cząstki w nim przemieszczają się do sąsiednich wierzchołków (w sposób kaskadowy). Cząstka piasku, która osiąga graniczny wierzchołek, znika w zlewie (`` spada ''). Jest to znane jako Abelowy model piaskowca .n × n
Problem: Ile czasu zajmuje konfiguracja, aby stała się powtarzalna pod względem , przy założeniu najgorszego algorytmu upuszczania cząstek piasku?n
W SODA '07 László Babai i Igor Gorodezky udowodnili, że tym razem są wielomianowo ograniczeni, ale ..
W SODA '12 Ayush Choure i Sundar Vishwanathan poprawili to ograniczenie do .O ( n7)
Ta odpowiedź wyglądałaby nieco lepiej, gdyby nie ich ulepszenie :)
źródło
Problem „wypukłej czaszki” polega na znalezieniu wypukłego wielokąta o maksymalnym polu wewnątrz danego prostego wielokąta. Najszybszy algorytm znany z tego problemu działa w czasie [Chang and Yap, DCG 1986].O ( n7)
źródło
Rozwiązanie Annihilation Games (Fraenkel i Yesha) ma złożoność .O ( n6)
źródło
Istnieje kilka niekonstruktywnych algorytmów, w szczególności
twierdzenieFellowsa i Langstonaoraz Courcelle'a.Ponadto algorytm liniowo-czasowy Bodlaendera dla szerokości drzewa i twierdzenie Courcelle'a są niezwykle niepraktyczne.
źródło
http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition
źródło
źródło
W prostokącie wielokąta, część 2: Minimalna liczba prostokątów tłuszczu , praktyczna modyfikacja problemu podziału prostokąta motywowana obawami w VLSI:
źródło
[1] Pytania dotyczące sztywności macierzy obliczeniowej
źródło
źródło