Złożoność obliczeniowa/Test 7: Algorytmy aproksymacyjne

Problemy NP-optymalizacyjne Problem NP-optymalizacyjny $\mathrm{\Pi }$

jest wersją optymalizacyjną pewnego problemu NP-zupełnego Źle

jest wersją optymalizacyjną pewnego problemu z klasy NP Źle

posiada wielomianowo obliczalną funkcję kosztu rozwiązania Dobrze

posiada wielomianową procedurę sprawdzania, czy dane rozwiązanie jest rozwiązaniem dopuszczalnym Dobrze

Stała aproksymacji Jeśli $A$ jest algorytmem $4/5$-aproksymacyjnym dla problemu maksymalizacji $\mathrm{\Pi }$, to

$A$ jest algorytmem optymalizacyjnym dla $\mathrm{\Pi }$ Źle

$A$ jest algorytmem $5/6$-aproksymacyjnym dla $\mathrm{\Pi }$ Źle

$A$ jest algorytmem $3/4$-aproksymacyjnym dla $\mathrm{\Pi }$ Dobrze

z definicji, jest to sytuacja niemożliwa Źle

Algorytm skojarzeniowy dla pokrycia wierzchołkowego Algorytm skojarzeniowy dla pokrycia wierzchołkowego

znajduje zawsze rozwiązanie optymalne Źle

jest algorytmem $5/2$-aproksymacyjnym Dobrze

jest algorytmem $15/8$-aproksymacyjnym Źle

nigdy nie znajduje rozwiązania optymalnego Źle

Aproksymacja dla problemu maksymalnego przekroju<quiz> Algorytm zachłanny dla problemu MAX CUT

posiada stałą aproksymacji równą 2 Źle

posiada stałą aproksymacji równą 1/2 Dobrze

nie posiada stałej aproksymacji Źle

nie ma złożoności wielomianowej Źle

Nieaproksymowalność problemu komiwojażera Wykazujemy, że problem komiwojażera nie posiada $a$-aproksymacji dla żadnej stałej $a$,

tylko przy założeniu $P\ne NP$ Dobrze

redukując problem cyklu Hamiltona Dobrze

redukując problem cyklu Eulera Źle

zacieśniając problem komiwojażera do instancji o kosztach krawędzi ograniczonych przez 2 Źle

Aproksymowalność problemu komiwojażera Problem komiwojażera ma strategię $a$-aproksymacyjną

jeśli spełniona jest nierówność trójkąta, dla $a=3/2$ Dobrze

jeśli spełniona jest nierówność trójkąta, wykorzystującą algorytm znajdowania skojarzenia w grafie dwudzielnym Źle

bez założenia o nierówności trójkata, dla $a=2$ Źle

dla pewnej stałej $a$, jeśli wagi krawędzi należą do zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle \1,2\ }} Dobrze

Strategia zachłanna dla problemu plecakowego Aproksymacyjny algorytm zachłanny dla problemu plecakowego

upakowuje najpierw elementy o największej wartości Źle

upakowuje najpierw elementy o najmniejszej wadze Źle

ma stałą aproksymacji równą 1/2 Źle

ma stałą aproksymacji równą 2 Źle

żadna z pozostałych odpowiedzi nie jest poprawna Dobrze