ARTP - 02 - Pokrývanie množinami

Zhrnutie prednášky

Prednáška uvádza aproximačné algoritmy ako nástroj na optimalizačné problémy, ktoré sú NP-ťažké, takže efektívny presný algoritmus nepoznáme. Na rozdiel od heuristík poskytujú záruku kvality: pri minimalizácii je výsledok najviac k-krát horší ako optimum, pri maximalizácii aspoň 1/k-krát optimum. Spomenuté je, že pre všeobecný problém obchodného cestujúceho k-aproximačný algoritmus neexistuje (ak P ≠ NP). Hlavnou témou je pokrývanie množinami (set cover), kde sa z daných podmnožín prvkov 1..n vyberá najmenší počet množín, ktorých zjednotenie pokrýva všetky prvky. Ilustruje sa objednávaním pizze pre skupinu a rozmiestnením strážnikov v budove, čo vedie k vrcholovému pokrytiu grafu ako špeciálnemu prípadu.

• - Aproximačné algoritmy riešia NP-ťažké optimalizačné problémy v polynomiálnom čase za cenu horšieho než optimálneho riešenia.
• - Na rozdiel od heuristík garantujú kvalitu: minimalizácia je najviac k-krát optimum, maximalizácia aspoň 1/k-krát optimum.
• - Pre všeobecný problém obchodného cestujúceho neexistuje k-aproximačný algoritmus, ak P ≠ NP.
• - Techniky aproximačných a pravdepodobnostných algoritmov sú rôznorodé, preto sa vyučujú cez príklady.
• - Pokrývanie množinami: vybrať najmenší počet množín, ktorých zjednotenie obsahuje všetky prvky.
• - Praktické príklady: objednávka pizze pre skupinu (prvky sú ľudia, množiny pizze) a strážnici v budove.
• - Vrcholové pokrytie grafu je špeciálny prípad pokrývania množinami, kde prvky sú hrany a množiny vrcholy.

Zhrnutie pripravené s pomocou AI z prepisu videa.