Czy są znane wyniki na temat złożoności znalezienia separatora (dowolnej wielkości) spełniającego daną właściwość? Wiem, że separator kliki jest łatwy do znalezienia (czas wielomianowy), a także wiem, że wiele artykułów rozważa problem znalezienia małych separatorów lub separatorów, które...
Istnieje program liniowy, dla którego chcę nie tylko rozwiązania, ale rozwiązania, które jest tak centralne, jak to możliwe na powierzchni polytopa, który przyjmuje minimalną wartość. Z góry oczekujemy, że minimalizująca powierzchnia powinna być wielowymiarowa z różnych powodów, w tym, że...
W Graphic TSP otrzymujesz nieważony niekierowany wykressolsolG a celem jest znalezienie najkrótszej trasy w solsolGktóry odwiedza każdy wierzchołek przynajmniej raz . Zauważ, że NIE jest to to samo, co znalezienie obwodu hamiltonowskiegosolsolG. Moje pytania to: Jaka jest złożoność Graphic TSP...
Chciałbym przeprosić wszystkie poniższe posty. Wybrałem niewłaściwe forum, aby pierwotnie to opublikować. Jednak zamiast uczynić to kompletnym marnotrawstwem, przerobiłem pytanie, aby było prawdziwym problemem „teoretycznej informatyki”. Problem: Utwórz algorytm, który pobiera zestaw n...
Według tytułu, oprócz korzystania z solwera LP ogólnego przeznaczenia, istnieje podejście do rozwiązywania układów nierówności względem zmiennych xja, ... ,xkxi,…,xkx_i, \ldots, x_k gdzie nierówności mają formę ∑ja ∈ jaxja<∑j ∈ Jxjot∑i∈Ixi<∑j∈Jxj\sum_{i \in I} x_i < \sum_{j \in J} x_j? Co ze...
Szukam twierdzenia, które mówi coś takiego: jeśli czas pokrycia odwracalnego łańcucha Markowa jest mały, to szczelina widmowa jest duża. Tutaj oznacza lukę widmową1 - |λ2)|1-|λ2)|1-|\lambda_2|oznacza to, że ignorujemy najmniejszą wartość własną łańcucha. Jedyny wynik, jaki udało mi się znaleźć w...
Szukam algorytmu do rysowania mieszanego wykresu okręgów / zależności (dla aplikacji językowych). Taki wykres miałby dwa różne typy wierzchołków (tokeny, węzły) i dwa różne typy krawędzi (hierarchiczne, niehierarchiczne). Jestem nowy w teorii grafów i algorytmach w ogóle i mam nadzieję, że to...
Background––––––––––––––Background_\underline{\bf Background} W 2005 r. Regev [1] wprowadził problem uczenia się z błędami (LWE), uogólnienie problemu parzystości uczenia się z błędem. Założenie o twardości tego problemu dla niektórych wyborów parametrów leży obecnie u podstaw dowodów...
Wiem, że oczekiwany najgorszy czas działania randomizowanego przyrostowego algorytmu triangulacji delauny (jak podano w geometrii obliczeniowej ) to . Istnieje ćwiczenie sugerujące, że najgorszym środowiskiem uruchomieniowym jest . Próbowałem skonstruować przykład, w którym tak naprawdę jest, ale...
Niech będzie wykresem. Niechbyć liczbą całkowitą. Niech będzie liczbą indukowanych przez krawędź posiadających wierzchołków i nieparzystą liczbę krawędzi. Niech będzie liczbą podgraphów indukowanych przez krawędź, mających wierzchołków i parzystą liczbę krawędzi. Niech . Problem ODD NAWET DELTA...
Dobrze wiadomo, że złożoność kwantowej kwerendy błędu ograniczonego funkcji to . Teraz pytanie brzmi: czy chcemy, aby nasz algorytm kwantowy odniósł sukces dla każdego wejścia z prawdopodobieństwem a nie ze zwykłą . Jeśli chodzi o jakie byłyby odpowiednie górne i dolne granice?O R (x1,x2), ......
Prowadzę kurs meta-heurystyki i muszę wygenerować ciekawe przykłady klasycznych problemów kombinatorycznych dla projektu semestralnego. Skupmy się na TSP. Zajmujemy się wykresami wymiarów200200200i większe. Próbowałem oczywiście wygenerować wykres z macierzą kosztów z wartościami pobranymi z...
Rozważ wykres ze wszystkimi krawędziami o pojemności jednostkowej. Można znaleźć min. Cięcie w czasie wielomianowym. Załóżmy, że mogę zwiększyć pojemność dowolnego kkkkrawędzie do nieskończoności (równoważne scalaniu węzłów po obu stronach krawędzi). Jaki jest optymalny sposób wyboru optymalnego...
Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych...
Proszę wybaczyć zwięzłość tytułu, mogłem poświęcić jasność na ołtarzu zwięzłości. Widać, że wstawienie elementów tablicy do binarnego drzewa wyszukiwania i ich ponowne odczytanie wymaga (przy wstawianiu) takich samych porównań, jak uruchomienie Quicksort na tej tablicy. Sekwencja osi przestawnych...
Rozwiązuję problem „mieszania” zestawów nakładających się obrazów. Te zestawy mogą być reprezentowane przez niekierowany ważony wykres, taki jak ten: Każdy węzeł reprezentuje obraz. Nakładające się obrazy są połączone krawędzią. Ciężar krawędzi reprezentuje wielkość obszaru nakładania się (...
Oto problem najbliższego sąsiada. Biorąc pod uwagę liczby rzeczywiste (bardzo duże !), Plus cel rzeczywisty , znajdź i których SUMA jest najbliższe . Umożliwiamy rozsądne wstępne przetwarzanie / indeksowanie (do ), ale w czasie zapytania (dane ) wynik powinien zostać zwrócony bardzo szybko (np....
Chcę podzielić zestaw punktów na dwa równe podzbiory, aby zminimalizować sumę kwadratów wewnątrz klastra. Możemy założyć, że punkty znajdują się w dwuwymiarowej przestrzeni euklidesowej. Mam nadzieję na coś szybszego niż ogólny algorytm grupowania k-średnich, biorąc pod uwagę, że k = d = 2. Czy...
Niech będzie wielomianem podanym przez obwód arytmetyczny o rozmiarze . Biorąc pod uwagę jako dane wejściowe, czy istnieje algorytm deterministyczny, aby sprawdzić, czy wszystkie nieredukowalne czynniki w są formami liniowymi? W pokrewnej uwadze, biorąc pod uwagę postać liniową , możemy sprawdzić...
Pozwolić d:{0,1}k×{0,1}k→Rd:{0,1}k×{0,1}k→Rd:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}być funkcją, którą nazywamy funkcją podobieństwa . Przykłady funkcji podobieństwa to odległość cosinus,l2l2l_2 norma, odległość Hamminga, podobieństwo Jaccard itp. Rozważać nnn binarne wektory długości kkk:...