Pytania otagowane jako semidefinite-programming

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 …
2
Jakie klasy programów matematycznych można rozwiązać dokładnie lub w przybliżeniu w czasie wielomianowym?
Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie rozwiązać, ale uważam, że ich definicja „wydajnego” nie pokrywa się z definicją TCS. …
2
Czy istnieje algorytm wielomianowy do określania, czy rozpiętość zbioru macierzy zawiera macierz permutacji?
Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji. Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne. EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne podejrzenia, że ​​gdyby istniało takie rozwiązanie, byłby to rodzaj algorytmu programowania …
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 …
1
Przyspieszenia wielomianowe z algorytmami opartymi na programowaniu półfinałowym
Jest to kontynuacja ostatniego pytania zadanego przez A. Pala: Rozwiązywanie programów półfinałowych w czasie wielomianowym . Nadal zastanawiam się nad faktycznym czasem działania algorytmów obliczających rozwiązanie programu półfinałowego (SDP). Jak zauważył Robin w swoim komentarzu do powyższego pytania, SDP-ów nie można ogólnie rozwiązać w czasie wielomianowym. Okazuje się, że jeśli …
1
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. …
3
Kiedy różnica w dualności programowania semidefinite (SDP) wynosi zero?
Nie udało mi się znaleźć w literaturze dokładnej charakterystyki zaniku luki dualności SDP. Lub kiedy ma miejsce „silna dualność”? Na przykład, kiedy ktoś porusza się między Lasserre a SOS SDP, w zasadzie ma się lukę w dualności. Jednak wydaje się, że istnieje jakiś „trywialny” powód, dla którego nie ma tej …
2
Co można rozwiązać za pomocą programowania półfinałowego, czego nie można rozwiązać za pomocą programowania liniowego?
Znam programy liniowe, ponieważ mogą one rozwiązywać problemy z liniowymi funkcjami celu i ograniczeniami liniowymi. Ale co programowanie półfinalne może rozwiązać, czego programowanie liniowe nie jest w stanie? Wiem już, że programy półfinałowe są uogólnieniem programów liniowych. Jak rozpoznać problem, który można rozwiązać za pomocą programowania półfinałowego? Jakiego typowego problemu …
1
Systematyczne badania sumy kwadratowych wielomianów podniesione do kwadratu
Zastanawiam się, czy istnieją systematyczne badania sum kwadratowych form kwadratowych, podobnych do form kwadratowych, co praktycznie znajduje odzwierciedlenie w rozkładzie wartości własnych (co ma ogromne praktyczne implikacje). Kilka przykładów związanych ze znaczeniem pytania. Analizy głównych składników (PCA) . Biorąc pod uwagę zestaw punktówxi∈Rn,i=1..kxi∈Rn,i=1..kx_i \in \mathbb{R^n}, i=1..k znajdź zestaw osi u1u1u_1, …
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.