Pytania otagowane jako approximation-hardness

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

2
Konsekwencje dolnych granic dla -net na przybliżeniu
Wielu tutaj prawdopodobnie zdaje sobie sprawę z ostatnich superliniowych dolnych granic Alon dla -net w naturalnych ustawieniach geometrycznych [PDF] . Chciałbym wiedzieć, co, jeśli w ogóle, taka dolna granica implikuje przybliżenie powiązanych problemów z zestawem Cover / Hitting Set. ϵϵ\epsilon Aby być nieco bardziej szczegółowym, rozważ rodzinę przestrzeni zasięgu, na …
1
Czysto teoretyczne objaśnienie redukcji z Unique Label Cover do Max-Cut
Studiuję Unique Games Conjecture i słynną redukcję do Max-Cut Khota i in. Ze swojej pracy i innych stron internetowych większość autorów używa (jak dla mnie) niejawnej równoważności między redukcją MAX-CUT a budowaniem konkretnych testów dla długich kodów. Z powodu mojego braku jasności co do tej równoważności staram się podążać tym …
2
Przybliżenie problemów trudnych do # P
Rozważ klasyczny problem # P-zupełny nr 3SAT, tj. Policz liczbę wycen, aby uzyskać 3CNF z nnnzmienne zadowalające. Interesuje mnie przybliżalność addytywna . Najwyraźniej istnieje prosty algorytm do osiągnięcia2)n - 12n−12^{n-1}- błąd, ale jeśli k &lt;2)n - 1k&lt;2n−1k<2^{n-1}, czy można mieć skuteczny algorytm aproksymacyjny, czy ten problem jest również trudny do …
3
Posadzona klika w G (n, p), zmieniająca się p
W przypadku problemu sadzonej kliki należy odzyskać kkk-klinka posadzona na losowym wykresie Erdosa-Renyi G ( n , p )G(n,p)G(n,p). To było głównie rozpatrywanep =12)p=12p=\frac{1}{2}, w którym to przypadku wiadomo, że można rozwiązać czas wielomianowy, jeśli k &gt;n--√k&gt;nk > \sqrt{n} i przypuszczalnie trudne k &lt;n--√k&lt;nk< \sqrt{n}. Moje pytanie brzmi: co wiadomo …
1
Czy Max-Cut APX-complete na grafach bez trójkątów?
W problemie Max-Cut szuka się podzbioru S wierzchołków danego prostego niekierowanego wykresu, tak że liczba krawędzi między S a dopełnieniem S jest tak duża, jak to możliwe. Max-Cut jest kompletny APX na wykresach ograniczonego stopnia [PY91], i faktycznie APX-kompletny na wykresach sześciennych (tj. Grafach stopnia 3) [AK00]. Max-Cut jest NP-kompletny …
2
Maksymalizacja sumarycznych wag krawędzi
Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane. Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że liczę krawędzie, które są wewnątrz podzbioru …
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.