optymalizacja kombinatoryczna

Wszystkie problemy optymalizacji kombinatorycznej, które dają się rozwiązać do optymalności w wielomianowym czasie

• muszą być matroidami

• muszą być z klasy NP

• mogą być matroidami

• muszą być z klasy P

Jeżeli P=NP to

• wszystkie problemy NP-trudne dadzą się rozwiązać w wielomianowym czasie

• żadne problemy NP-równoważne nie dadzą si rozwiązać w wielomianowym czasie

• wszystkie problemy NP-równoważne dadzą się rozwiązać w wielomianowym czasie

• żadne problemy NP-łatwe nie dadzą się rozwiązać w wielomianowym czasie

Jeżeli P nie jest równe NP (P!=NP) to

• wszystkie problemy NP-łatwe dadzą się rozwiązać w wielomianowym czasie

• wszystkie problemy NP-trudne dadzą się rozwiązać w wielomianowym czasie

• żadne problemy NP-łatwe nie dadzą się rozwiązać w wielomianowym czasie

• żadne problemy NP-trudne nie dadzą się rozwiązać w wielomianowym czasie

Wyobraźmy sobie, że dla problemu szeregowania zadań na równoległych identycznych procesorach dla kryterium długości uszeregowania (P||Cmax) podano wielomianowe algorytmy aproksymacyjne A,B spełniające dla każdej instancji I warunki 1) algorytm: A: |A(I)-OPT(I)|<=k, gdzie k>0 jest stałą, 2) algorytm B: B(I)/OPT(I)<=k, gdzie 1<k? Wynika z tego, że

• z 1) wynika, że P=NP, z 2) wynika, że P!=NP

• z 1) wynika, że P=NP, z 2) nic nie wynika

• z 1) nic nie wynika, z 2) wynika, że P=N

• z 1) wynika, że P!=NP, z 2) wynika, że P=NP

Problem optymalizacji kombinatorycznej jest nieaproksymowalny gdy

• jest NP-trudny

• nie jest znany dla niego wielomianowy algorytm o skończonym oszacowaniu jakości

• można wykazać, że nie istnieje dla niego wielomianowy algorytm o skończonym oszacowaniu

• istnieje dla niego wielomianowy algorytm o skończonym oszacowaniu jakości

• istnienie dla niego wielomianowego algorytmu o gwarantowanej jakości pociągałoby P=NP

Przetarg między jakością rozwiązań i czasem wykonania w poprawnie skonstruowanym algorytmie dla problemu optymalizacji kombinatorycznej oznacza, że:

• im krótszy czas działania tym lepszej jakości rozwiązania

• dobrej jakości rozwiązanie są łatwe do uzyskania w krótkim czasie

• im dłuższy czas działania tym lepszej jakości rozwiązania

• z upływem czasu jakość rozwiązania się ustala

W kolejnych iteracjach algorytmu Dinica kolejne sieci warstwowe mają

• stałą liczbę warstw

• niemalejącą liczbę warstw

• rosnącą liczbę warstw

• liczba warstw nie ma związku z numerem iteracji w algorytmie Dinica

Jeżeli w grafie istnieje cykl o ujemnej długości, to

• między niektórymi wierzchołkami da się a między innymi nie da się określić odległości

• wszystkie najkrótsze ścieżki w grafie przechodzą przez ten cykl

• między wszystkim wierzchołkami da się określić odległość

• między żadnymi wierzchołkami nie da się określić odległości

Porównując algorytmy zachłanne i dokładne dla problemów optymalizacji kombinatorycznej

• tylko algorytmy dokładne dają gwarancję optymalności rozwiązań

• tylko algorytmy zachłanne dają gwarancję optymalności

• ani algorytmy dokładne ani zachłanne nie dają gwarancji optymalności rozwiązań

• ani algorytmy dokładne ani zachłanne nie dają gwarancji optymalności rozwiązań

• Wykładnicze są algorytmy dokładne, zachłanne są wielomianowe

Wyobraźmy sobie, że 1) dla problemu wierzchołkowego kolorowania grafu podano wielomianowy algorytm A dla każdej instancji I spełniający warunek A(I)/OPT(I)<4/3, 2) dla problemu krawędziowego kolorowania grafu podano wielomianowy algorytm B spełniający warunek: |B(I)-OPT(I)|≤k. Gdzie 0<k<2 jest stałą, A(I), B(I) oznaczają jakość rozwiązań aproksymacyjnych, OPT(I) wartość optymalna. Z tego wynika, że

• z 1) wynika, że P=NP, z 2) wynika że P!=NP

• z 1) wynika, że P!=NP, z 2) wynika że P=NP

• z 1) wynika, że P=NP, z 2) nic nie wynika

• z 1) nic nie wynika, z 2) wynika, że P=NP