Pytania dotyczące algorytmów aproksymacyjnych.
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...
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...
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...
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...
G=(V,E,w)G = (V, E, w)w:E→Rw:E\rightarrow \mathbb{R}arg max S ⊂ V ∑ ( u , v ) ∈ E : u ∈ S , v ∉ S w ( u , v ) w ( e ) ≥ 0 e ∈ EargmaxS⊂V∑(u,v)∈E:u∈S,v∉Sw(u,v)\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)w(e)≥0w(e) \geq 0e∈Ee \in E Odbiór losowego podzbioru wierzchołki...
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...
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...
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...
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...
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...
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...
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...
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...
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...
Ostatnio zacząłem szukać algorytmów aproksymacyjnych dla problemów trudnych dla NP i zastanawiałem się nad teoretycznymi przyczynami ich badania. (To pytanie nie ma być zapalne - jestem po prostu ciekawy). Z badań algorytmów aproksymacyjnych wynikła pewna naprawdę piękna teoria - związek między...
Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są...
Dla konkretności rozważ LP za rozwiązanie gry dla dwóch graczy o sumie zerowej, w której każdy gracz ma akcji. Załóżmy, że każdy zapis macierzy wypłat ma najwyżej 1 wartość bezwzględną. Dla uproszczenia nie róbmy żadnych założeń sparity.nnnZAZAA Załóżmy, że środowisko wykonawcze jest dostępne w...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Gdy weźmiemy pod uwagę algorytm aproksymacji dla problemu minimalizacji, luka integralności formuły IP dla tego problemu daje dolną granicę współczynnika aproksymacji dla pewnej klasy algorytmów (takich jak algorytm zaokrąglania lub pierwotny podwójny). W rzeczywistości istnieje wiele problemów,...
Biorąc pod uwagę zestaw S macierzy permutacji nxn (który jest tylko małą częścią n! Możliwych macierzy permutacji), w jaki sposób możemy znaleźć podzbiory T o minimalnej wielkości, tak że dodanie macierzy T ma co najmniej 1 w każdej pozycji? Interesuje mnie ten problem, w którym S jest małą...