Pytania otagowane jako approximation

Pytania dotyczące algorytmów, które rozwiązują problemy z pewnym ograniczonym błędem.

3
Problemy decyzyjne a „rzeczywiste” problemy, które nie są „tak lub nie”
Czytałem w wielu miejscach, że niektóre problemy są trudne do przybliżenia ( NP jest trudne do przybliżenia ). Ale przybliżenie nie jest problemem decyzyjnym: odpowiedź jest liczbą rzeczywistą, a nie Tak lub Nie. Również dla każdego pożądanego współczynnika przybliżenia istnieje wiele odpowiedzi, które są poprawne, a wiele błędnych, a to …
3
Dlaczego problemy związane z NP są tak różne pod względem ich przybliżenia?
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 oszacowania niż inne. Dobrym przykładem jest TSP. Chociaż …
3
Przybliżenie złożoności Kołmogorowa
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 podobieństwa). W takim przypadku zastosowano kompresory danych w celu przybliżenia złożoności …
3
Dlaczego nie ma algorytmów aproksymacyjnych dla SAT i innych problemów decyzyjnych?
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 dla takich problemów. Szukałem w szczególności SAT i na stronie …
1
Przybliżenie minimalnej przepustowości drzew binarnych
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 przepustowości. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978 . …
2
Co to jest algorytm aproksymacji bicriteria?
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 pracy znajdują się odniesienia, ale żadne z nich nie wyjaśnia, czym jest algorytm aproksymacji …
1
Dlaczego wszystkie problemy w FPTAS występują również w FPT?
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 przybliżenia, podczas gdy FPT charakteryzuje problemy na …
1
Średnia długość ścieżek st (prostych) na skierowanym wykresie
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ż odpowiednie wyniki na specjalnych wykresach.
1
Optymalizacja matematyczna funkcji głośnej
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 \mathbb{R}^df(x)f(x)f(x) Gdybym miał procedurę oceny na dowolnym …
2
Czy ten kombinatoryczny problem optymalizacji jest podobny do jakiegokolwiek znanego problemu?
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 aby łączna suma wartości komórek …
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.