Teoretyczne informatyka approximation-algorithms

3

Jakie są problemy z najlepszym współczynnikiem aproksymacji uzyskanym przez algorytm zwracający jednolicie losowe rozwiązanie?

Jakie są problemy z najlepiej znanym współczynnikiem aproksymacji osiągniętym przez algorytm zwracający jednolicie losowe rozwiązanie? Znam jeden taki przykład problemu : w artykule „ Tight Bounds for Permutation Flow Shop Scheduling ” Viswanath Nagarajan i Maxim Sviridenko udowodnili, że losowa sekwencja zadań ma gwarancję 2 √fa| perm | dom a …

12 ds.algorithms reference-request approximation-algorithms

3

Czy istnieje algorytm online do śledzenia komponentów na zmieniającym się niekierowanym wykresie?

Problem Mam nieukierunkowany wykres (z wieloma krawędziami), który z czasem się zmieni, węzły i krawędzie można wstawiać i usuwać. Przy każdej modyfikacji wykresu muszę aktualizować połączone elementy tego wykresu. Nieruchomości Dodatkowe właściwości polegają na tym, że żadne dwa składniki nigdy nie zostaną ponownie połączone. Oczywiście wykres może mieć dowolne cykle …

12 ds.algorithms graph-theory approximation-algorithms online-algorithms

1

zmaksymalizować MST (G [S]) na wszystkich indukowanych podgraphach G [S] na wykresie metrycznym

Czy ten problem był już badany? Biorąc pod uwagę metryczny niekierowany wykres G (długości krawędzi spełniają nierówność trójkąta), znajdź zestaw S wierzchołków, tak że MST (G [S]) jest zmaksymalizowany, gdzie MST (G [S]) jest minimalnym drzewem rozpinającym podgrafu wywołanym przez S. Czy ten problem był już badany? Czy to trudne …

11 ds.algorithms graph-algorithms np-hardness approximation-algorithms

2

Znajdź wszystkie pary wartości bliskich odległości Hamminga

Mam kilka milionów wartości 32-bitowych. Dla każdej wartości chcę znaleźć wszystkie inne wartości w odległości Hamminga wynoszącej 5. W podejściu naiwnym wymaga to porównań O(N2)O(N2)O(N^2) , których chcę uniknąć. Uświadomiłem sobie, że jeśli potraktowałem te 32-bitowe wartości jako liczby całkowite i posortowałem listę raz, to wartości, które różniły się tylko …

11 ds.algorithms co.combinatorics approximation-algorithms

3

min uderzenie zestawu każdej podstawy matroidu

Dostajemy matroida. Naszym celem jest znalezienie zestawu elementów o minimalnym rozmiarze, który ma niepuste przecięcie z każdą podstawą matroidu. Czy problem był już badany? Czy to jest w P? Na przykład w matroidach drzew przestawnych minimalny zestaw uderzeń powinien być minimalnym cięciem. Dzięki.

11 co.combinatorics approximation-algorithms optimization

5

Czy istnieje jakakolwiek technika polegająca na wyszukiwaniu absolutnego minimum (maksimum) funkcji w przestrzeni wielowymiarowej?

Znam algorytm spadku gradientu, który może znaleźć lokalne minimum (maksimum) danej funkcji. Czy jest jakaś modyfikacja spadku gradientu, która pozwala znaleźć absolutne minimum (maksimum), gdzie funkcja ma kilka ekstremów lokalnych? Czy istnieją jakieś ogólne techniki, jak ulepszyć algorytm, który może znaleźć ekstremum lokalne, w celu znalezienia ekstremum ekstremalnego?

11 ds.algorithms approximation-algorithms machine-learning

1

Dlaczego problemy z uzupełnianiem NP nie mają podobnych współczynników aproksymacji?

Ponieważ 2 problemy NP-zupełne są z definicji redukowalne względem siebie, więc rozwiązanie jednego z nich można uzyskać za pomocą czarnej skrzynki rozwiązującej drugi, dlaczego nie mają podobnych współczynników aproksymacji (w odniesieniu do ich odpowiedników optymalizacyjnych )? Wydaje mi się, że pewne stałe lub nawet wielomianowe znoszenie może być zrozumiane, ale …

11 cc.complexity-theory approximation-algorithms reductions

2

Średnie osadzenia zniekształceń

Rozważmy dwie przestrzenie metrycznych i ( Y , F ) i z obszaru wstawiania ľ : X → Y . Tradycyjne osadzanie przestrzeni metrycznej mierzy jakość μ jako najgorszy stosunek pierwotnej odległości do odległości końcowej: ρ = max p , q ∈ X { d ( x , y )( …

11 approximation-algorithms cg.comp-geom embeddings

2

Jakiś szybki algorytm problemu z ustawieniem łuku zwrotnego przy minimalnych kosztach?

Na ukierunkowanym wykresie , F ⊂ E , jeśli G ∖ F jest DAG (ukierunkowany wykres acykliczny), F nazywa się zestawem łuku zwrotnego. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Jeżeli każda krawędź jest powiązana z wagą , problem z zestawem łukowym sprzężenia zwrotnego przy minimalnym koszcie polega na znalezieniu F takiej, że W …

11 ds.data-structures graph-theory np-hardness approximation-algorithms

4

Redukcja wymiarów z luzem?

Johnson-Lindenstrauss lemat mówi przybliżeniu że każdy zbiór z n punktów R d , istnieje mapę F : R d → R k , gdzie k = O ( log n / ε 2 ) tak, że dla wszystkich x , y ∈ S : ( 1 - ϵ ) | …

11 ds.algorithms approximation-algorithms cg.comp-geom metrics embeddings

4

Algorytmy aproksymacyjne stosowane w algorytmach dokładnych

Algorytmy aproksymacyjne mogą dawać wynik do pewnego stałego współczynnika. Jest to nieco mniej satysfakcjonujące niż dokładne algorytmy. Jednak stałe czynniki są ignorowane w złożoności czasowej. Zastanawiam się więc, czy następująca sztuczka jest możliwa lub została zastosowana, aby rozwiązać jakiś problem :B ∘ Ab∘ZAB \circ A Użyj algorytmu aproksymacyjnego rozwiązującego problem …

11 ds.algorithms big-list approximation-algorithms

5

Funkcje submodularne: żądanie referencyjne

Byłbym bardzo zainteresowany odniesieniami do teorii funkcji podmodularnych (od podstaw po zaawansowane). W szczególności studiuję aproksymacje do problemów z twardą optymalizacją i chcę rozwinąć swoje podstawy w funkcjach podmodularnych, ponieważ są one istotne dla problemów optymalizacji, które badałem. Z góry dziękuję.

11 ds.algorithms reference-request approximation-algorithms optimization

1

Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań

Rozważ następujący problem. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj …

10 approximation-algorithms randomized-algorithms search-problem random-walks binary-trees

2

Złożoność znalezienia punktu Borsuk-Ulam

Twierdzenie Borsuka-Ulama mówi, że dla każdej ciągłej funkcji nieparzystej sfery n do e-przestrzeni istnieje punkt taki, że .x 0 g ( x 0 ) = 0solsolgx0x0x_0sol( x0) = 0sol(x0)=0g(x_0)=0 Simmons i Su (2002) opisują metodę aproksymacji punktu za pomocą lematu Tuckera . Jednak nie jest jasne, jaka jest złożoność ich …

10 approximation-algorithms time-complexity topology algebraic-topology

1

Jakie są wyniki algorytmów szacujących wielomiany dla danego zestawu punktów?

Wydaje się, że istnieje wiele randomizowanych algorytmów do testowania tożsamości wielomianowej, sprawdzających, czy dany wielomian ma wartość zero. Czy są jakieś wyniki algorytmów, które dokonują pewnego rodzaju oszacowania wielomianów w określonym zestawie punktów? Może to być na przykład przybliżenie, dla jakiej części tych punktów wielomian ocenia się na zero, lub …

10 ds.algorithms approximation-algorithms randomized-algorithms derandomization polynomials

Pytania otagowane jako approximation-algorithms