Pytania otagowane jako approximation-algorithms

Pytania dotyczące algorytmów aproksymacyjnych.

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
Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?
Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym? Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w …
1
Dobre referencje na temat przybliżonych metod rozwiązywania problemów logicznych
Wiadomo, że wiele problemów logicznych (np. Problemy satysfakcji kilku logik modalnych) nie są rozstrzygalne. Istnieje również wiele nierozstrzygalnych problemów w teorii algorytmów, np. W optymalizacji kombinatorycznej. Ale w praktyce heurystyki i algorytmy przybliżone działają dobrze w przypadku algorytmów praktycznych. Można więc oczekiwać, że odpowiednie będą również algorytmy przybliżone dla problemów …
2
Zależność między stałym parametrem a algorytmem aproksymacyjnym
Stały parametr i przybliżenie to zupełnie inne podejścia do rozwiązywania trudnych problemów. Mają inną motywację. Przybliżenie szuka szybszego wyniku dzięki przybliżonemu rozwiązaniu. Naprawiono parametr szuka dokładnego rozwiązania ze złożonością czasową pod względem wykładniczej lub jakiejś funkcji k i funkcji wielomianowej n, gdzie n jest wielkością wejściową, a k jest parametrem. …
2
Jak nazywa się ten wariant problemu z ustawieniem pokrycia zestawu?
Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli .UUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełniafaF{\cal F}ZA= { E1, E2), … , E| ZA|}A={E1,E2,…,E|A|}{\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\} 1) ,∀ E∈ A, …
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ć …
2
Przybliżone zabarwienie wykresu z obiecaną górną granicą na maksymalnym niezależnym zestawie
W mojej pracy powstaje następujący problem: Czy istnieje znany algorytm, który aproksymuje liczbę chromatyczną wykresu bez niezależnego zestawu rzędów 65? (Więc alfa (G) <= 64 jest znane, a | V | / 64 jest trywialną dolną, | V | trywialną górną granicą. Ale czy istnieją lepiej udowodnione przybliżenia w tych …
3
Problem wielokrotnego cięcia
Szukam nazwy lub jakichkolwiek odniesień do tego problemu. Biorąc pod uwagę wykres ważony G=(V,E,w)G=(V,E,w)G = (V, E, w) znajdź podział wierzchołków na n=|V|n=|V|n = |V|ustawia S1,…,SnS1,…,SnS_1,\ldots,S_n tak, aby zmaksymalizować wartość przyciętych krawędzi: c(S1,…,Sn)=∑i≠j⎛⎝∑(u,v)∈E:u∈Si,v∈Sjw(u,v)⎞⎠c(S1,…,Sn)=∑i≠j(∑(u,v)∈E:u∈Si,v∈Sjw(u,v))c(S_1,\ldots,S_n) = \sum_{i \ne j}\left(\sum_{(u,v)\in E : u \in S_i, v \in S_j}w(u,v)\right) Zauważ, że niektóre zestawySiSiS_imogą być …
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.