Teoretyczne informatyka reference-request

2

Rozszerzenia twierdzenia Ramseya: monochromatyczne, ale różnorodne

Jako kontynuacja mojego poprzedniego pytania , które rozwiązał Hsien-Chih Chang, oto kolejna próba znalezienia odpowiedniego uogólnienia twierdzenia Ramseya. (Nie musisz czytać poprzedniego pytania; ten post jest samodzielny.) Parametry: podane są liczby całkowite , a następnie jest wybierane jako wystarczająco duże. Terminologia: podzbiór jest podzbiorem rozmiaru .1≪d≪k≪n1≪d≪k≪n1 \ll d \ll k …

9 reference-request co.combinatorics ramsey-theory

1

Twardość NP specjalnego przypadku problemu upakowania ortogonalnego

Pozwolić VVV być zestawem DDD-wymiarowe kształty prostokątne. Dlad∈{1,...,D}d∈{1,...,D}d \in \{1,...,D\} i v∈Vv∈Vv \in V, wd(v)∈Q+wd(v)∈Q+w_d(v) \in \mathbb{Q}^{+} opisuje długość vvv w wymiarze ddd. Ta sama notacja jest używana dla konteneraCCC. TheDDD-wymiarowy problem pakowania ortogonalnego (OPP-DDD) ma zdecydować, czy VVV pasuje do pojemnika CCCbez nakładania się. Formalnie rzecz biorąc, problemem jest …

9 cc.complexity-theory reference-request np-hardness packing

2

Testowanie właściwości dla niezależnych zestawów

Załóżmy, że otrzymaliśmy wykres GGG i parametry k,ϵk,ϵk,\epsilon. Czy istnieją zakresy wartości dlakkk (czy jest to wykonalne dla wszystkich kkk), dla których można sprawdzić, czy GGG jest ϵϵ\epsilon-dużo posiadania niezależnego zestawu przynajmniej wielkości kkk w samą porę O(n+poly(1/ϵ))O(n+poly(1/ϵ))O(n + \text{poly}(1/\epsilon)) ? Jeśli użyjemy zwykłego pojęcia ϵϵ\epsilon-dale (tj. co najwyżej ϵn2ϵn2\epsilon …

9 ds.algorithms graph-theory reference-request property-testing

1

Algorytmy przeszukiwania baz danych teorii wykresów metrycznych

(Powoli) piszę recenzję Podręcznika algorytmów chemoinformatycznych dla SIGACT News. Jeden rozdział omawia bieżące implementacje oprogramowania, a wyszukiwania w bazie danych (i inne aplikacje) wydają się nie wykorzystywać tak dużej ilości informacji o wykresach, jak mogłyby. Z drugiej strony być może bardziej teoretyczne algorytmy byłyby zbyt trudne do wdrożenia. Wygląda jednak …

9 reference-request

Pytania otagowane jako reference-request