Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Znalezienie krótkich i grubych ścieżek
Motywacja: W standardowych algorytmach maksymalnego przepływu ścieżki augmentacyjnej wewnętrzna pętla wymaga znalezienia ścieżek od źródła do zatonięcia na ukierunkowanym, ważonym wykresie. Teoretycznie dobrze wiadomo, że aby algorytm nawet zakończył działanie, gdy istnieją nieracjonalne pojemności krawędzi, musimy nałożyć ograniczenia na ścieżki, które znajdziemy. Na przykład algorytm Edmondsa-Karpa mówi nam, aby znaleźć …
2
Przybliżanie nietrywialnego automorfizmu grafów?
Wykres automorfizmem jest permutacją węzłów wykres indukuje bijection na zestawie krawędź EEE . Formalnie jest to permutacja fff węzłów takich jak (u,v)∈E(u,v)∈E(u,v)\in E iff (f(u),f(v))∈E(f(u),f(v))∈E(f(u),f(v))\in E Zdefiniuj naruszoną krawędź dla pewnej permutacji jako krawędź odwzorowana na inną niż krawędź lub krawędź, której preimage nie jest krawędzią. Dane wejściowe : niesztywny …
1
CSP z nieograniczoną ułamkową szerokością hipertree
za´za´\acute{\rm a}H ∈ P T I M EH.H.HH.H.H∈ P.T.jaM.mi∈P.T.jaM.mi\in PTIME Definicje itp. Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!). Niech H.H.H będzie hipergrafatem. Następnie dla hipergraph H.H.H i mapowania γ: E( H) → [ 0 , ∞ )γ:mi(H.)→[0,∞)\gamma : E(H) \rightarrow [0,\infty) …
3
Algorytmy obliczania równowagi Nasha.
Przeszukałem forum, aby sprawdzić, czy zostało to już zadane, i chociaż omawiamy teorię gier algorytmicznych, nie mogłem znaleźć rozwiązania tego konkretnego problemu. Próbuję dowiedzieć się, jaki jest najbardziej znany algorytm obliczania przybliżonej (mieszanej strategii) równowagi Nasha w skończonej grze n-person. Oczywiście algorytmem tym byłby PPAD. Bardziej interesuje mnie szybkość / …
4
Interesujące funkcje na wykresach, które można skutecznie zmaksymalizować.
Powiedz, że mam wykres ważony G=(V,E,w)G=(V,E,w)G = (V,E,w) taki, że w:E→[−1,1]w:E→[−1,1]w:E\rightarrow [-1,1] jest funkcją ważenia - zwróć uwagę, że dopuszczalne są wagi ujemne. Powiedzieć, że f:2V→Rf:2V→Rf:2^V\rightarrow \mathbb{R} definiuje właściwość każdego podzbioru wierzchołków S⊂VS⊂VS \subset V . fffargmaxS⊆Vf(S)arg⁡maxS⊆Vf(S)\arg\max_{S \subseteq V}f(S) Na przykład funkcja cięcia wykresu jest interesującą właściwością podzbiorów wierzchołków, ale …
2
Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją?
Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją? Jeśli nie, to jak można zdefiniować taką klasę? Wiemy, że wiele problemów ma swoją wersję online: np. Wersja online problemu pakowania bin. Problemy online są trudniejsze, ponieważ mierzone są ich współczynnikami konkurencyjności. I nie znalazłem niczego podobnego …
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 …
2
NP-kompletne warianty nierozwiązywalnych problemów?
Przykłady ograniczone -Complete wariantów nierozstrzygalnych zestawach:N.P.NPNP Ograniczony problem zatrzymania = { | Maszyna NTM M zatrzymuje się i przyjmuje x w ciągu t kroków}( M, x , 1t)(M,x,1t)(M, x, 1^t)M.MMxxxttt Ograniczone płytki = { | jest płytki kwadratu o powierzchni t 2 za pomocą płytek z T }( T, 1t)(T,1t)(T, …
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.