Twardość przybliżenia
W informatyce twardość aproksymacji to dziedzina, która bada algorytmiczną złożoność znajdowania prawie optymalnych rozwiązań problemów optymalizacyjnych .
Zakres
Twardość aproksymacji uzupełnia badanie algorytmów aproksymacji , udowadniając, dla niektórych problemów, granicę czynników, za pomocą których można skutecznie przybliżyć ich rozwiązanie. Zazwyczaj takie granice pokazują współczynnik przybliżenia, powyżej którego problem staje się NP-trudny , co sugeruje, że znalezienie przybliżenia problemu w czasie wielomianowym jest niemożliwe, chyba że NP=P . Pewna twardość wyników aproksymacji jest jednak oparta na innych hipotezach, wśród których godną uwagi jest hipoteza o unikalnych grach .
Historia
Od wczesnych lat siedemdziesiątych wiadomo było, że wielu problemów optymalizacyjnych nie można rozwiązać w czasie wielomianowym, chyba że P = NP , ale w wielu z tych problemów rozwiązanie optymalne można było skutecznie przybliżyć do pewnego stopnia. W latach siedemdziesiątych Teofilo F. Gonzalez i Sartaj Sahni rozpoczęli badanie twardości aproksymacji, pokazując, że pewne problemy optymalizacyjne były NP-trudne nawet do przybliżenia w ramach danego współczynnika aproksymacji . Oznacza to, że dla tych problemów istnieje próg taki, że dowolne przybliżenie w czasie wielomianowym ze współczynnikiem aproksymacji poza tym progiem może być użyte do rozwiązania problemów NP-zupełnych w czasie wielomianowym. Na początku lat 90., wraz z rozwojem PCP , stało się jasne, że o wiele więcej problemów aproksymacji jest trudnych do przybliżenia i że (chyba że P = NP) wiele znanych algorytmów aproksymacji osiąga najlepszy możliwy współczynnik aproksymacji.
Teoria twardości aproksymacji zajmuje się badaniem progu aproksymacji takich problemów.
Przykłady
Aby zapoznać się z przykładem problemu optymalizacji NP-trudnego, który jest trudny do przybliżenia, zobacz zestaw okładek .
Zobacz też
Dalsza lektura
- Trevisan, Luca (27 lipca 2004), Niezbliżenie problemów optymalizacji kombinatorycznej (PDF)
Linki zewnętrzne
- CSE 533: The PCP Theorem and Hardness of Approximation, jesień 2005 , program nauczania z University of Washington , Venkatesan Guruswami i Ryan O'Donnell