Rozwiązywanie programów półfinałowych w czasie wielomianowym

Wiemy, że programy liniowe (LP) można rozwiązać dokładnie w czasie wielomianowym za pomocą metody elipsoidy lub metody punktu wewnętrznego, takiej jak algorytm Karmarkara. Niektóre LP z super-wielomianową (wykładniczą) liczbą zmiennych / ograniczeń można również rozwiązać w czasie wielomianowym, pod warunkiem, że możemy dla nich zaprojektować wielomianową wyrocznię z separacją czasu.

Co z programami półfinałowymi (SDP)? Jakie klasy SDP można rozwiązać dokładnie w czasie wielomianowym? Kiedy SDP nie da się dokładnie rozwiązać, czy zawsze możemy zaprojektować FPTAS / PTAS do jego rozwiązania? Jakie są warunki techniczne, w których można to zrobić? Czy możemy rozwiązać SDP z wykładniczą liczbą zmiennych / ograniczeń w czasie wielomianowym, jeśli możemy zaprojektować dla niego wielomianową wyrocznię z separacją czasu?

Czy możemy skutecznie rozwiązać SDP występujące w kombinatorycznych problemach optymalizacyjnych (MAX-CUT, kolorowanie grafów)? Jeśli możemy rozwiązać tylko w czynnikiem, nie będzie to miało wpływ na stałych algorytmów aproksymacji (jak współczynnik 0,878 dla Goemans-Williamson MAX-CUT Algorithm)? $1+\epsilon$

Wszelkie dobre referencje będą mile widziane.

linear-programming semidefinite-programming convex-optimization Arindam Pal
źródło

W rzeczywistości metoda ta działa ogólnie na programowanie wypukłe

Suresh Venkat

Istnieją co najmniej dwa powody, dla których nie można rozwiązać ogólnego SDP w czasie wielomianowym. (1) Istnieją SDP, których rozwiązanie ma wielkość wykładniczą. (2) SDP mogą kodować sumę problemu pierwiastków kwadratowych, o którym nie wiadomo, że jest rozwiązaniem wielomianowym.

Robin Kothari,

@RobinKothari W przypadku SDP, zwykle „rozwiązany w czasie wielomianowym” jest zastępowany przez „wchodzi w

(dodatek) do OPT w czasie wielomianowym w

” IIRC. ps w jaki sposób SDP koduje pierwiastek kwadratowy?

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

Suresh Venkat

@SureshVenkat: Powiedzmy, że mamy macierz 2x2 z wpisami [ab; Płyta CD]. Załóżmy, że jest to dodatnia półfinał id = 1. Oznacza to, że b = c oraz a> = b ^ 2. Więc b jest górną granicą pierwiastka kwadratowego z. Teraz możemy zmaksymalizować sumę kilku takich b. Optymalna wartość będzie sumą pierwiastków kwadratowych odpowiednich a.

Robin Kothari,

To nie jest multiplikatywne, ale addytywne. Ponadto, en.wikipedia.org/wiki/Semidefinite_programming#Al Algorytmy

Suresh Venkat

Rozwiązywanie programów półfinałowych w czasie wielomianowym

Odpowiedzi: