Pytania dotyczące algorytmów, które rozwiązują problemy z pewnym ograniczonym błędem.
Szukam algorytmu do dystrybucji wartości z listy, aby powstała lista była jak najbardziej „zrównoważona” lub „równomiernie rozłożona” (w cudzysłowie, ponieważ nie jestem pewien, czy są to najlepsze sposoby na opisanie jej ... później przedstawię sposób pomiaru, czy wynik jest lepszy niż inny). Tak...
Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich...
Chciałbym rozpocząć pytanie od stwierdzenia, że jestem programistą i nie mam dużego doświadczenia w teorii złożoności. Jedną z rzeczy, które zauważyłem, jest to, że o ile wiele problemów jest NP-zupełnych, o tyle w przypadku problemów z optymalizacją niektóre są znacznie trudniejsze do...
Mam problem z decyzją o zakończeniu NP. Biorąc pod uwagę przykład problemu, chciałbym zaprojektować algorytm, który wyświetli TAK, jeśli problem jest wykonalny, i NIE, w przeciwnym razie. (Oczywiście, jeśli algorytm nie jest optymalny, popełni błędy.) Nie mogę znaleźć algorytmów aproksymacyjnych...
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji...
Patrzyłem na tę stronę i mówi, że ludzie znaleźli rozwiązania dla wycieczek TSP, które są tylko o 0,031% wyższe niż optymalna wycieczka. Bez znalezienia optymalnej trasy, skąd wiedzą, jaka to powinna być
Z tego, co przeczytałem w preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Oto definicja PTAS : Wielomianowy schemat aproksymacji czasu ( PTAS ) dla problemu jest...
Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?t s tssstttsssttt Pomocne mogą być również...
Zgodnie z artykułem Wikipedii na temat schematów aproksymacji czasu wielomianowego : Wszystkie problemy w FPTAS są możliwe do rozwiązania ze stałymi parametrami. Ten wynik mnie zaskakuje - te klasy wydają się zupełnie różne od siebie. FPTAS charakteryzuje problemy na podstawie ich łatwości do...
Co to jest algorytm aproksymacji bicriteria? Nadal pojawia się to w przypadku klastrowania strumienia danych. Czy ma to związek z optymalizacją wielu celów? Właśnie tam natknąłem się na: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Artykuł dotyczy strumieniowej wersji algorytmu k-średnich. W...
Niech będzie jakimś problemem liczenia, o którym wiadomo, że to # -Complete .ΠΠ\PiP.P.P Czy to oznacza, że jest -hard (czyli nie PTA dla istnieje problem chyba że )?ΠΠ\PiA P.XZAP.XAPXP.=
Problem jest następujący: Mamy dwuwymiarową tablicę / siatkę liczb, z których każda reprezentuje pewną „korzyść” lub „zysk”. Także ma dwie nieruchome całkowite i h (jako „szerokość” i „wysokość”). A stałej całkowitej n .wwwhhhnnn Teraz chcą nałożyć prostokątów o wymiarach szer × h na siatce, tak...
Niech będzie funkcją, która jest dość ładna (np. Ciągła, różniczkowalna, niezbyt wiele lokalnych maksimów, może wklęsła itp.). Chcę znaleźć maksima f : wartość x ∈ R d, która sprawia, że f ( x ) jest tak duże, jak to możliwe.f:Rd→Rf:Rd→Rf:\mathbb{R}^d \to \mathbb{R}fffx∈Rdx∈Rdx \in...
Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Muszę udowodnić, że istnieje st is twardy dla każdego
Biorąc pod uwagę (binarny) program liczbowy w postaci:0 , 10,10,1 minśwfa( x )A x = bxja≥ 0xja∈ { 0 , 1 }∀ i∀ iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall...