Pytania otagowane jako approximation-algorithms

Pytania dotyczące algorytmów aproksymacyjnych.

3
Czy istnieje rozsądne pojęcie algorytmu aproksymacyjnego dla nierozwiązywalnego problemu?
Niektóre problemy są nierozstrzygalne, ale mimo to można poczynić pewne postępy w ich rozwiązywaniu. Na przykład problem zatrzymania jest nierozstrzygalny, ale można poczynić praktyczne postępy w tworzeniu narzędzi do wykrywania potencjalnych nieskończonych pętli w kodzie. Problemy z układaniem płytek są często nierozstrzygalne (np. Czy ta płytka poliomino ma jakiś prostokąt?), …
4
Algorytmy aproksymacyjne dla metrycznego TSP
Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż 1231.51.51.5 w czasie wielomianowym. Czy coś wiadomo na temat znajdowania rozwiązań aproksymacyjnych w czasie wykładniczym (na przykład mniej niż2nkroków z tylko przestrzenią wielomianową)? Np. W jakim czasie i przestrzeni możemy znaleźć trasę, której odległość …
8
Znaczenie luki w integralności
Zawsze miałem problem ze zrozumieniem znaczenia luki integralności (IG) i ją ograniczam. IG jest stosunkiem (jakości) optymalnej liczby całkowitej do (jakości) optymalnego rzeczywistego rozwiązania złagodzenia problemu. Rozważmy przykrycie wierzchołków (VC) jako przykład. VC można określić jako znalezienie optymalnego rozwiązania liczb całkowitych następującego zestawu równań liniowych: Mamy zero / jednego o …
9
Optymalne algorytmy zachłanne dla problemów trudnych dla NP
Chciwość z braku lepszego słowa jest dobra. Jednym z pierwszych paradygmatów algorytmicznych nauczanym na kursie algorytmów wprowadzających jest podejście zachłanne . Chciwe podejście skutkuje prostymi i intuicyjnymi algorytmami dla wielu problemów w P. Co ciekawe, dla niektórych problemów trudnych dla NP oczywisty i naturalny chciwy / lokalny algorytm skutkuje (możliwym) …
11
Algorytmy aproksymacyjne dla problemów w P.
Zwykle myśli się o zbliżeniu rozwiązań (z gwarancjami) do problemów trudnych dla NP. Czy trwają badania nad zbliżeniem problemów, o których wiadomo, że są w P? To może być dobry pomysł z kilku powodów. Z góry mojej głowy algorytm aproksymacyjny może działać ze znacznie mniejszą złożonością (lub nawet znacznie mniejszą …
1
Przykłady zabawek dla solverów Plotkin-Shmoys-Tardos i Arora-Kale
Chciałbym zrozumieć, w jaki sposób solver Arora-Kale SDP aproksymuje relaksację Goemansa-Williamsona w prawie liniowym czasie, jak solver Plotkin-Shmoys-Tardos aproksymuje ułamkowe problemy „upakowania” i „pokrycia” w prawie liniowym czasie oraz jak algorytmy są instancjami abstrakcyjnych ram „uczenia się od ekspertów”. Teza Kale'a ma doskonałą prezentację, ale bardzo trudno mi przejść bezpośrednio …
4
Algorytmy kwantowej aproksymacji
Ogólnie uważa się za mało prawdopodobne, aby komputery kwantowe były w stanie skutecznie rozwiązywać problemy związane z NP. W klasycznym przypadku jednym podejściem do rozwiązania takich problemów jest zastosowanie algorytmów aproksymacyjnych. Czy były jakieś badania algorytmów aproksymacyjnych wykorzystujących obliczenia kwantowe, w których kwantowość znacznie przyspiesza w porównaniu z klasycznymi metodami …
4
Kompendium najlepszych wyników aproksymacji i twardości dla problemów optymalizacji NP
Czy znasz jakieś aktualne wiki poświęcone problemom z optymalizacją NP z najlepszym wynikiem przybliżenia i twardości? Na podstawie informacji zwrotnych wydaje się, że można bezpiecznie założyć, że nie ma takiego zasobu (zobacz dwie odpowiedzi na końcu tego pytania). - dodano 8 lutego. Ponieważ w ciągu ostatnich dwóch dziesięcioleci pojawiło się …
3
Kiedy odprężenie się liczy?
Załóżmy, że rozwiązujemy problem zliczania prawidłowych zabarwień, licząc ważone zabarwienia w następujący sposób: każde prawidłowe zabarwienie otrzymuje wagę 1, a każde niewłaściwe zabarwienie otrzymuje wagę gdzie jest w pewnym stopniu stałe, a to liczba krawędzi z punktami końcowymi ma ten sam kolor. Gdy zmienia się na 0, sprowadza się to …
4
Zakres ograniczonej liczności ograniczonej obejmuje: twardość aproksymacji
Rozważ problem minimalnego pokrycia zestawu z następującymi ograniczeniami: każdy zestaw zawiera co najwyżej kkk elementów, a każdy element wszechświata występuje w co najwyżej zestawach fff Na przykład: w przypadku k=4k=4k = 4 i f=2f=2f = 2 odpowiada minimalnej wierzchołek problemu pokrywy na wykresach z maksymalnym stopniem 4. Niech a(k,f)>1a(k,f)>1a(k,f) > …
2
Twierdzenie o uniwersalnej aproksymacji - sieci neuronowe
Opublikowałem to wcześniej na MSE, ale zasugerowano, że może być lepsze miejsce do zapytania. Uniwersalne twierdzenie o aproksymacji stwierdza, że ​​„standardowa wielowarstwowa sieć przesyłowa z pojedynczą ukrytą warstwą, która zawiera skończoną liczbę ukrytych neuronów, jest uniwersalnym aproksymatorem wśród funkcji ciągłych na zwartych podzbiorach Rn, przy łagodnych założeniach dotyczących funkcji aktywacji”. …
5
Algorytmy aproksymacji dla maksymalnego niezależnego zestawu na specjalnych klasach wykresów
Wiemy, że maksymalny niezależny zestaw (MIS) jest trudny do przybliżenia przy współczynniku dla dowolnego ϵ > 0, chyba że P = NP. Jakie są specjalne klasy wykresów, dla których znane są lepsze algorytmy aproksymacyjne?n1−ϵn1−ϵn^{1-\epsilon}ϵ>0ϵ>0\epsilon > 0 Jakie są wykresy, dla których znane są algorytmy wielomianowe? Wiem, że dla idealnych wykresów …
3
Źródło edukacyjne lub ankieta na temat analizy programu półfinałowego?
Podczas projektowania algorytmów aproksymacyjnych czasami rozwiązuje się program półfinałowy, po którym następuje etap zaokrąglania. Często ilustrowanym przykładem jest Max-Cut. (Zobacz np. Algorytmy aproksymacji Vijay Vazirani.) Czy istnieją dobre źródła edukacyjne lub ankiety wykraczające poza problem Max-Cut w celu wyjaśnienia bardziej złożonych algorytmów zaokrąglania i technik wykorzystywanych do ich analizy? Mam …
2
Algorytmy aproksymacji czasu wielomianowego do planowania maszyny: ile pozostało otwartych problemów?
W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc świetnie i przydatne, gdyby każdy z nas mógł sporządzić …
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.