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

Problem NP-optymalizacyjny $\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

Jeśli $A$ jest algorytmem $4/5$-aproksymacyjnym dla problemu maksymalizacji $\Pi$, to

$A$ jest algorytmem optymalizacyjnym dla $\Pi$ Źle

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

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

z definicji, jest to sytuacja niemożliwa Źle

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

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

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

tylko przy założeniu $P\neq 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

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 $1,2$ Dobrze

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