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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Problem NP-optymalizacyjny

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 jest algorytmem -aproksymacyjnym dla problemu maksymalizacji , to

jest algorytmem optymalizacyjnym dla

jest algorytmem -aproksymacyjnym dla

jest algorytmem -aproksymacyjnym dla

z definicji, jest to sytuacja niemożliwa


Algorytm skojarzeniowy dla pokrycia wierzchołkowego

znajduje zawsze rozwiązanie optymalne

jest algorytmem -aproksymacyjnym

jest algorytmem -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 -aproksymacji dla żadnej stałej ,

tylko przy założeniu

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ę -aproksymacyjną

jeśli spełniona jest nierówność trójkąta, dla

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

dla pewnej stałej , jeśli wagi krawędzi należą do zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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