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) optymalnym współczynnikiem aproksymacji (przy odpowiednich założeniach teoretycznych złożoności). Klasycznym przykładem jest problem z ustawieniem okładki . Naturalny algorytm zachłanny podaje współczynnik aproksymacji O (ln n), który jest optymalny, chyba że P = NP.

Wymień niektóre naturalne algorytmy chciwe / lokalne dla problemów trudnych dla NP, które są możliwe do udowodnienia, optymalne przy założeniach teoretycznych o odpowiedniej złożoności.

Metodę warunkowych oczekiwań (dla derandomizacji algorytmów „losowego przypisywania” dla Max-Cut i Max-SAT) można postrzegać jako chciwą strategię: dla , wybierasz wartość zmiennej takiej oczekiwana liczba ograniczeń spełnionych w powstałej zredukowanej instancji przekracza oczekiwaną liczbę ograniczeń spełnionych w bieżącej instancji. (W rzeczywistości, chciwy algorytm dla aproksymacji Max-Cut jest taki sam jak algorytm „metody warunkowych oczekiwań” dla aproksymacji Max-Cut.)x ı 1 / 2 1 /$i=1,\ldots,n$$x_i$$1/2$$1/2$

Ponieważ metoda działa również dla Max-E3-SAT i osiąga aproksymację , jest to przykład chciwego algorytmu, który jest optymalnym przybliżeniem, chyba że (por. Wyniki Happada i Moshkovitza-Raza dla Max- E3-SAT).P = N $7/8$$P=NP$

Pokrywa wierzchołków: Najlepszy algorytm aproksymacji współczynnika stałego polega (łapczywie) na znalezieniu maksymalnego dopasowania i wybraniu wszystkich wierzchołków zaangażowanych jako przybliżone rozwiązanie. Daje to rozwiązanie przybliżone do 2 i żadne lepsze przybliżenie o stałym współczynniku nie jest możliwe, chyba że hipoteza unikalnych gier jest fałszywa.

Subhash Khot i Oded Regev, pokrycie wierzchołków może być trudne do przybliżenia w granicach 2 ε , JCSS 74 (3), 2008.

Poza tematem: Myślę, że jest to naprawdę ładny algorytm aproksymacyjny, zwłaszcza, że ​​jest on tak trywialny z korzyścią z perspektywy czasu.

Biorąc pod uwagę ukierunkowany wykres, znajdź acykliczny podgraph z maksymalną liczbą krawędzi.

Trywialny algorytm 2-aproksymacyjny: Wybierz dowolne uporządkowanie wierzchołków i weź krawędzie przednie lub tylne.

Pokonanie 2-przybliżenia jest znane z trudnych gier Unique (chociaż może nie być trudne NP).

• Pokonanie losowego porządku jest trudne: niedopuszczalność maksymalnego acyklicznego subgrrafu Venkatesan Guruswami, Rajsekar Manokaran i Prasad Raghavendra.

Podmodularna maksymalizacja w odniesieniu do ograniczenia liczności ma chciwe przybliżenie 1-1 / e. Algorytm wynika z Nemhauser, Wolsey, Fisher. Twardość NP wynika z twardości np. Pokrycia zestawu, ponieważ maksymalne pokrycie jest szczególnym przypadkiem maksymalizacji podmodularnej.

Chciwy daje przybliżenie (1-1 / e) do Max-k-cover, i nie można tego poprawić, chyba że P = NP.

Znalezienie minimalnego stopnia MST. Jest to trudne, ponieważ znalezienie ścieżki hamiltonowskiej jest szczególnym przypadkiem. Lokalny algorytm wyszukiwania daje w ramach stałej addytywnej 1.

Odniesienie

Przybliżenie drzewa Steinera o minimalnym stopniu do jednego z optymalnych

$k$$G = (V,E)$$d_{ij} \geq 0$$i,j \in V$$k$

$k$$S \subseteq V, |S| = k$$k$$k$$k$$r$$r$

$i \in V$$S$$|S| < k$$j \in V$$d(j,S)$$S$$|S| = k$

$2$$k$$\rho$$\rho < 2$$P = NP$$k$$k$$2$

$P|prec|C_{max}$

Warunkowa twardość pierwszeństwa Ograniczone szeregowanie na identycznych maszynach autorstwa Oli Svensson

Być może to Cię również zainteresuje (dostosowane z metod do tłumaczenia globalnych ograniczeń na lokalne )

Ponieważ chciwe metody (dokładniej metody lokalne ) wykorzystują tylko informacje lokalne, aby osiągnąć globalną optymalizację, jeśli zostaną znalezione sposoby, które są w stanie przekształcić warunki globalne w warunki, które można wykorzystywać z wykorzystaniem tylko informacji lokalnych, zapewnia to (globalnie) optymalne rozwiązanie problemów używając tylko chciwych / lokalnych technik.

Referencje:

1. Myśl globalnie, dopasuj lokalnie: bezobsługowe uczenie się nisko wymiarowych kolektorów (Journal of Machine Learning Research 4 (2003))
2. Globalna optymalizacja z wykorzystaniem lokalnych informacji z aplikacjami do kontroli przepływu, Bartal, Y.
3. Dlaczego naturalny gradient ?, Amari S., Douglas SC
4. Lokalna optymalizacja globalnych celów: konkurencyjne rozproszone rozwiązanie impasu i alokacja zasobów, Awerbuch, Baruch, Azar, Y.
5. Uczenie się ze spójnością lokalną i globalną
6. Problemy z satysfakcją z ograniczeń można rozwiązać za pomocą lokalnych metod spójności

Istnieje kilka odniesień, które dotyczą problemu tłumaczenia globalnych funkcji oceny (lub ograniczeń) na lokalne (przy użyciu lokalnych informacji) i ich spójności (tj. Konwergencji do tego samego globalnego optimum):

1. Lokalne funkcje oceny i globalne funkcje oceny dla ewolucji obliczeniowej, HAN Jing, 2003
2. Wyłonił się z funkcji oceny lokalnej, Han Jing i Cai Qingsheng, 2002

Streszczenie (od 1. powyżej)

W tym artykule przedstawiono nowe spojrzenie na ewolucję obliczeniową z punktu widzenia lokalizacji i globalności funkcji oceny w celu rozwiązania klasycznego problemu kombinatorycznego: problemu kcolorowania (problem decyzyjny) i problemu minimalnego zabarwienia (problem optymalizacji). Najpierw sprawdzamy aktualne algorytmy i modelujemy problem kolorowania jako system wieloagentowy. Następnie wykazujemy, że zasadnicza różnica między tradycyjnymi algorytmami (wyszukiwanie lokalne, takie jak Symulowane wyżarzanie) a algorytmami rozproszonymi (takimi jak model Alife i AER) polega na funkcji oceny: Symulowane wyżarzanie wykorzystuje informacje globalne do oceny stanu całego systemu, który nazywa się metoda globalnej funkcji oceny (GEF); model Alife & AER wykorzystuje informacje lokalne do oceny stanu pojedynczego agenta, która nazywa się metodą Local Evaluation Function (LEF). Porównujemy wyniki metod LEF i GEF w rozwiązywaniu problemów z k-kolorowaniem i minimalnych problemów z barwieniem. Komputerowe wyniki eksperymentów pokazują, że LEF jest porównywalny z metodami GEF (Symulowane wyżarzanie i zachłanne), w wielu przypadkach problemowych LEF pokonuje metody GEF. Jednocześnie analizujemy związek między GEF i LEF: spójność i niespójność. Twierdzenie o spójności pokazuje, że równowaga Nasha LEF jest identyczna z lokalnymi optymami GEF, gdy LEF jest zgodny z GEF. Twierdzenie to częściowo wyjaśnia, dlaczego LEF może doprowadzić system do globalnego celu. Proponowane są niektóre zasady konstruowania spójnego LEF. Oprócz spójności

W szczególności w artykule omówiono metody określania, czy funkcja lokalna (LEF) jest spójna z funkcją globalną (GEF) oraz metody konstruowania spójnych LEF z danych GEF ( twierdzenie o spójności ).

Fragment sekcji Wnioski (od 1. powyżej)

Ten artykuł to dopiero początek badań LEF i GEF. Oprócz powyższego raportu z badań jest jeszcze wiele przyszłych prac: więcej eksperymentów na metodach LEF; badanie analityczne dotyczące LEF; wystarczalność lokalnych informacji dla LEF; oraz istnienie spójnego GEF dla dowolnego LEF; Czy koncepcja spójności jest wystarczająca? Ponieważ algorytmy genetyczne mają również funkcję oceny (funkcję sprawności), czy możemy zastosować LEF i GEF do algorytmów genetycznych? … Naszym celem jest przestudiowanie i próba odpowiedzi na wszystkie te pytania