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

From Studia Informatyczne

Problem NP-optymalizacyjny \Pi

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

jest wersją optymalizacyjną pewnego problemu z klasy NP

posiada wielomianowo obliczalną funkcję kosztu rozwiązania

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


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

A jest algorytmem optymalizacyjnym dla \Pi

A jest algorytmem 5/6-aproksymacyjnym dla \Pi

A jest algorytmem 3/4-aproksymacyjnym dla \Pi

z definicji, jest to sytuacja niemożliwa


Algorytm skojarzeniowy dla pokrycia wierzchołkowego

znajduje zawsze rozwiązanie optymalne

jest algorytmem 5/2-aproksymacyjnym

jest algorytmem 15/8-aproksymacyjnym

nigdy nie znajduje rozwiązania optymalnego


Algorytm zachłanny dla problemu MAX CUT

posiada stałą aproksymacji równą 2

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

nie posiada stałej aproksymacji

nie ma złożoności wielomianowej


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

tylko przy założeniu P\neq NP

redukując problem cyklu Hamiltona

redukując problem cyklu Eulera

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


Problem komiwojażera ma strategię a-aproksymacyjną

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

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

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

dla pewnej stałej a, jeśli wagi krawędzi należą do zbioru \1,2\ }


Aproksymacyjny algorytm zachłanny dla problemu plecakowego

upakowuje najpierw elementy o największej wartości

upakowuje najpierw elementy o najmniejszej wadze

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

ma stałą aproksymacji równą 2

żadna z pozostałych odpowiedzi nie jest poprawna