Pytania oznaczone «approximation-hardness»

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

32
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...

22
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...

16
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...

15
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...

14
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 -> b seq ⊥ b =...