Pytania otagowane jako approximation-hardness

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

9
Optymalne algorytmy zachłanne dla problemów trudnych dla NP
Chciwość z braku lepszego słowa jest dobra. Jednym z pierwszych paradygmatów algorytmicznych nauczanym na kursie algorytmów wprowadzających jest podejście zachłanne . Chciwe podejście skutkuje prostymi i intuicyjnymi algorytmami dla wielu problemów w P. Co ciekawe, dla niektórych problemów trudnych dla NP oczywisty i naturalny chciwy / lokalny algorytm skutkuje (możliwym) …
4
Twardość aproksymacji bez twierdzenia PCP
Ważnym zastosowaniem twierdzenia PCP jest to, że daje wyniki typu „twardość aproksymacji”. W niektórych stosunkowo prostszych przypadkach można udowodnić taką twardość bez PCP. Czy jest jednak jakikolwiek przypadek, w którym twardość wyniku aproksymacji została najpierw udowodniona przy użyciu twierdzenia PCP, tj. Wynik nie był wcześniej znany, ale później znaleziono bardziej …
4
Twardość aproksymacji przy założeniu NP! = CoNP
Dwa typowe założenia potwierdzające twardość wyników aproksymacji to i Unique Games Conjecture. Czy jest jakaś twardość wyników aproksymacji przy założeniu, że ? Szukam problemu takiego, że „trudno jest zbliżyć do współczynnika chyba że ”.P≠NPP≠NPP \neq NPNP≠coNPNP≠coNPNP \neq coNPAAAAAAαα\alphaNP=coNPNP=coNPNP = coNP Wiadomym jest, że „pokazuje współczynnik NP twardość najkrótszym problemu wektora …
1
Czy Gap-3SAT NP-zupełny jest nawet dla formuł 3CNF, w których żadna para zmiennych nie pojawia się w znacznie większej liczbie klauzul niż średnia?
W tym pytaniu formuła 3CNF oznacza formułę CNF, w której każda klauzula obejmuje dokładnie trzy różne zmienne. Dla stałych 0 < s <1, Gap-3SAT s stanowi następujący problem: GAP 3SAT s wystąpienia : a 3CNF wzór φ. Tak, obietnica : φ jest satysfakcjonująca. No-obietnica : Brak przypisania prawda spełniać więcej …
4
Kompendium najlepszych wyników aproksymacji i twardości dla problemów optymalizacji NP
Czy znasz jakieś aktualne wiki poświęcone problemom z optymalizacją NP z najlepszym wynikiem przybliżenia i twardości? Na podstawie informacji zwrotnych wydaje się, że można bezpiecznie założyć, że nie ma takiego zasobu (zobacz dwie odpowiedzi na końcu tego pytania). - dodano 8 lutego. Ponieważ w ciągu ostatnich dwóch dziesięcioleci pojawiło się …
3
Kiedy odprężenie się liczy?
Załóżmy, że rozwiązujemy problem zliczania prawidłowych zabarwień, licząc ważone zabarwienia w następujący sposób: każde prawidłowe zabarwienie otrzymuje wagę 1, a każde niewłaściwe zabarwienie otrzymuje wagę gdzie jest w pewnym stopniu stałe, a to liczba krawędzi z punktami końcowymi ma ten sam kolor. Gdy zmienia się na 0, sprowadza się to …
3
Twardość aproksymacji - błąd addytywny
Istnieje bogata literatura i co najmniej jedna bardzo dobra książka określająca znaną twardość wyników przybliżenia dla problemów trudnych dla NP w kontekście błędu multiplikatywnego (np. 2-przybliżenie dla pokrywy wierzchołków jest optymalne przy założeniu UGC). Obejmuje to również dobrze zrozumiałe klasy złożoności aproksymacji, takie jak APX, PTAS i tak dalej. Co …
1
Czym jest twardość UG i czym różni się od twardości NP w oparciu o unikalną hipotezę gier?
Istnieje wiele niedopuszczalności wyników, które opierają się na unikalnym założeniu gier. Na przykład, Zakładając unikalną hipotezę gier, NP jest trudne do przybliżenia maksymalnego problemu cięcia w ramach współczynnika R dla dowolnej stałej R > R GW . (Tutaj R GW = 0,878… jest współczynnikiem przybliżenia algorytmu Goemans – Williamson.) Jednak …
2
Algorytmy aproksymacji czasu wielomianowego do planowania maszyny: ile pozostało otwartych problemów?
W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc świetnie i przydatne, gdyby każdy z nas mógł sporządzić …
3
Dlaczego różnicowe współczynniki aproksymacji nie są dobrze zbadane w porównaniu ze standardowymi pomimo deklarowanych korzyści?
Istnieje standardowa teoria aproksymacji, w której stosunek aproksymacji wynosi supAOPTsupAOPT\sup\frac{A}{OPT} (dla problemów zcelamiMINMINMIN),AAA- wartość zwracana przez niektóre algorytmyAAAiOPTOPTOPT- wartość optymalna. I inna teoria, żeprzybliżenie różnicowe,gdzie stosunek przybliżenia wynosiinfΩ−AΩ−OPTinfΩ−AΩ−OPT\inf\frac{\Omega-A}{\Omega-OPT} ,ΩΩ\Omega- najgorsza wartość wykonalnego rozwiązania dla danego wystąpienia. Doautorówz tego twierdzenia teorii, że ma jakieś konkretne korzyści w stosunku do klasycznego jednego. …
3
Twardość UGC predykatu
Tło : W oryginalnym dokumencie UGC Subhash Khota ( PDF ) udowadnia trudność UG w podejmowaniu decyzji, czy dana instancja CSP z ograniczeniami w całej formie Niezupełna (a, b, c) w stosunku do trójskładnikowego alfabetu przyznaje zadanie spełniające 1 - ograniczeń lub czy nie ma zadowalających zadań 8ϵϵ\epsilonograniczeń, dla dowolnie …
2
Przybliżenie w czasie podwykonawczym
Istnieją badania dotyczące algorytmów aproksymacyjnych dla całkowitych problemów NP w czasie wielomianowym i dokładnych algorytmów w czasie wykładniczym. Czy istnieją badania na temat algorytmów aproksymacyjnych dla kompletnych problemów NP w podwykładniczym czasie formy gdzie δ 2 ∈ ( 0 , 1 ) ?2nδ22nδ22^{n^{\delta_2}}δ2∈(0,1)δ2∈(0,1)\delta_2\in(0,1) Szczególnie interesuje mnie to, co wiadomo 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.