ARTP - 06 - Zložitosť aproximačných algoritmov

Zhrnutie prednášky

Posledná prednáška o aproximačných algoritmoch predstavuje hierarchiu optimalizačných tried PO, FPTAS, PTAS, APX a NPO a pripomína, že všeobecný problém obchodného cestujúceho nemá konštantnú aproximáciu, ak P ≠ NP. Pri dôkazoch neaproximovateľnosti sa používa podobný princíp ako pri polynomiálnych redukciách pri NP-ťažkosti, no vychádza sa z problému MAX-3-SAT. Základný výsledok hovorí, že existuje ε > 0 a polynomiálna transformácia formuly F na formulu F', pri ktorej je pre splniteľnú F splniteľných všetkých m klauzúl, inak najviac (1−ε)·m. Tým vzniká zakázaná medzera, vďaka ktorej by (1−ε)-aproximačný algoritmus dokázal rozlíšiť splniteľné a nesplniteľné formuly, čo smeruje k dôkazu neexistencie PTAS.

• - Hierarchia tried: PO ⊆ FPTAS ⊆ PTAS ⊆ APX ⊆ NPO.
• - NPO je optimalizačný ekvivalent NP; PO je optimalizačný ekvivalent P.
• - FPTAS vyžaduje čas polynomiálny vo veľkosti vstupu aj v 1/ε (príklad: problém batohu), PTAS iba vo veľkosti vstupu (príklad: balenie do krabíc).
• - APX zahŕňa problémy s konštantným aproximačným faktorom, napr. metrické TSP, vrcholové pokrytie a MAX-SAT.
• - Všeobecné TSP nemá konštantnú aproximáciu, ak P ≠ NP (redukcia z Hamiltonovskej kružnice).
• - Východiskovým problémom pre dôkazy neaproximovateľnosti je MAX-3-SAT s transformáciou, ktorá vytvára zakázanú medzeru medzi (1−ε)·m a m splnenými klauzulami.
• - Aproximačný algoritmus s faktorom 1−ε pre MAX-3-SAT by dokázal rozlíšiť splniteľné formuly od nesplniteľných, čo by viedlo k P = NP.

Zhrnutie pripravené s pomocou AI z prepisu videa.