Pytania otagowane jako approximation-hardness

Twardość aproksymacji, czyli niedokładność.

1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
1
Czy kompletność PSPACE oznacza twardość aproksymacyjną?
W komentarzu w innym poście z cstheorySE wspomniano, że kompletność PSPACE implikuje twardość APX. Czy ktoś może wyjaśnić / udostępnić referencję? Czy to jest „ciasne”? (tj. czy istnieją problemy kompletne z PSPACE, których problem optymalizacji dopuszcza stałe przybliżanie współczynnika w czasie wielopunktowym? Co z kompletnością dla pewnego poziomu PH? Czy …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
1
Płynna analiza algorytmów aproksymacyjnych
Wygładzona analiza była stosowana wiele razy, aby zrozumieć czas działania dokładnych algorytmów dla wielu problemów, takich jak programowanie liniowe i k-średnich. Istnieją dość ogólne wyniki w tej dziedzinie, na przykład Heiko Röglin i Berthold Vöcking, Analiza wygładzania programowania liczb całkowitych , 2005. Niektóre z tych ogólnych wyników wydają się polegać …
1
Prawie zawsze prawie w porządku
Szukam klasy złożoności, który dotyczy APX jako BPP dotyczy P. Już samo pytanie tutaj , ale być może będzie TCS być bardziej owocne lokalizacja odpowiedzi. Powodem tego pytania jest to, że w praktycznych problemach często trzeba znaleźć przybliżone odpowiedzi (a więc APX) z wystarczająco wysoką pewnością (a więc BPP), co …
2
Które gry 2P1R są potencjalnie ostre?
Dwukomorowe gry na jedną rundę (2P1R) są niezbędnym narzędziem do uzyskania stopnia zbliżenia. Konkretnie, równoległe powtarzanie dwóch rundowych gier z dwiema proverami pozwala zwiększyć rozmiar luki w decyzyjnej wersji problemu aproksymacji. Zobacz wywiad ankiety Ran Raz na CCC 2010, aby uzyskać przegląd tego tematu. Równoległe powtarzanie gry ma zadziwiającą właściwość …
2
Twardość separatorów wierzchołków
Dla danego wykresu problem separatora pyta, czy istnieje zbiór wierzchołków lub krawędzi o małej liczności (lub wadze), którego usunięcie dzieli G na dwa rozłączne wykresy o w przybliżeniu równych rozmiarach. Nazywa się to problemem separatora wierzchołków, gdy usunięty zestaw jest zestawem wierzchołków, a problemem separatora krawędzi, gdy jest zestawem krawędzi. …
3
Kiedy różnica w dualności programowania semidefinite (SDP) wynosi zero?
Nie udało mi się znaleźć w literaturze dokładnej charakterystyki zaniku luki dualności SDP. Lub kiedy ma miejsce „silna dualność”? Na przykład, kiedy ktoś porusza się między Lasserre a SOS SDP, w zasadzie ma się lukę w dualności. Jednak wydaje się, że istnieje jakiś „trywialny” powód, dla którego nie ma tej …
2
Istnienie
Rozważ problem z zestawem dominującym na ogólnych wykresach i niech będzie liczbą wierzchołków na wykresie. Chciwy algorytm aproksymacji daje gwarancję aproksymacji współczynnika , tzn. Możliwe jest znalezienie w czasie wielomianowym rozwiązania takiego, że , gdzie jest rozmiarem minimalnego zestawu dominującego. Istnieją ograniczenia wskazujące, że nie możemy poprawić zależności od dużo …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.