Optymalne algorytmy zachłanne dla problemów trudnych dla NP

38

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.

Shiva Kintali
źródło
Suresh (lub) Ryan, czy możesz dodać tag o nazwie „twardość przybliżenia” i oznaczyć to pytanie. Nie mogę dodawać nowych tagów z moją obecną reputacją :( Ponadto, ponieważ długie tagi (> 20 znaków) są niedozwolone, wydaje mi się, że powinno to być twardość około.
Shiva Kintali
Cześć Shiva, dodałem tag twardości w przybliżeniu, jak sugerowałeś, ale osobiście uważam, że twardość w przybliżeniu brzmi ładniej i powinna być możliwa, ponieważ jest krótsza niż algorytmy aproksymacyjne.
Kaveh
6
Dobrze wybrane pierwsze zdanie. ;)
AlcubierreDrive,

Odpowiedzi:

19

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 / 2i=1,,nxi1/21/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 P7/8P=NP

Ryan Williams
źródło
16

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.

gphilip
źródło
1
czy algorytm maksymalnego dopasowania jest naprawdę zachłanny?
Suresh Venkat,
Tak, ponieważ zapewnia lokalnie optymalny wybór na każdym kroku. Algorytm faktycznie dokonuje wyboru lokalnego / wykonalnego /, ale ponieważ krawędzie są nieważone, jest to również optymalny wybór.
gphilip
11

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.
Jagadish
źródło
11

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.

Ashwinkumar BV
źródło
1
Analiza zachłannego algorytmu przez Nemhauser-Wolsey-Fisher dotyczy tylko maksymalizacji, z zastrzeżeniem prostego ograniczenia liczności. Chciwy daje tylko aproksymacji nawet dla prostego matroida partycji. -approximation dla maksymalizacji funkcji do submodular zastrzeżeniem arbitralnej matroid jest ostatnim rezultatem powodu Vondrák i inni (w tym ja). Opiera się na kilku narzędziach i nie jest chciwym algorytmem. ( 1 - 1 / e )1/2(11/e)
Chandra Chekuri,
Oczywiście, mój błąd. Edytowałem odpowiedź, aby odzwierciedlić poprawkę.
Ashwinkumar BV,
10

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

Lew Reyzin
źródło
Myślę, że jest to ten sam problem, co odpowiedź @ AshwinkumarBV, którą, jak sądzę, opublikowano podczas pisania mojej ...
Lev Reyzin
6

kG=(V,E)dij0i,jVk

kSV,|S|=kkkkrr

iVS|S|<kjVd(j,S)S|S|=k

2kρρ<2P=NPkk2

Juho
źródło
1

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

Nikos M.
źródło