Kapitola 1
Státnice - Aproximační algoritmy a schémata

1.1 Aproximační algoritmy

Definice (Aproximační algoritmus)

Aproximační algoritmus běží v polynomiálním čase a vrací řešení “blízká” optimu. Je nutné mít nějakou míru kvality řešení. Označme:

- hodnotu optimálního řešení

- hodnotu nalezenou aproximačním algoritmem

A předpokládejme nezáporné hodnoty řešení.

Definice (Poměrová chyba)

Řekneme, že algoritmus řeší problém s poměrovou chybou , pokud pro každé zadání velikosti platí:

Definice (Relativní chyba)

Řekneme, že algoritmus řeší problém s relativní chybou , pokud pro každé zadání velikosti platí:

Poznámka (O převodu chyb)

Z jedné chyby se dá vyjádřit druhá:

- V případě maximalizační úlohy:

- V případě minimalizační úlohy:

Příklad (Aproximační algoritmy pro vrcholové pokrytí)

- “Brát vrcholy od nejvyššího stupně, dokud nemám celé pokrytí” nemá konstantní relativní chybu – ex. protipříklad, kdy

- “Vzít libovolnou hranu, dát do pokrytí její dva konce, odstranit její incidentní hrany a projít tak celé ” má relativní chybu – žádné 2 hrany nemají společný vrchol, tj. mám pokrytí o velikosti mn. disj. hran. Každé vrcholové pokrytí je ale mn. disj. hran.

Příklad (Aproximační algoritmy pro TSP)

Omezení na trojúhelníkovou nerovnost – pořád je NP (převod HKTSP zachovával trojúhelníkovou nerovnost). Algoritmus:

1. Najdi minimální kostru

2. Zvol lib. vrchol a pomocí DFS nad v PRE-ORDERu očísluj vrcholy.

3. Cesta (s opakováním) po kostře přes všechny vrcholy . Pak (každou hranou kostry jdu tam a zpět).

4. Výslednou HK vyrobím zkrácením cesty (vypouštěním již navštívených vrcholů), z trojúhelníkové nerovnosti . Celkem tedy dává , protože ( je kostra, bez jedné hrany).

Bez omezení – pro žádné konstantní neexistuje polynomiální algoritmus, řešící obecný TSP s poměrovou chybou . Mohu totiž mít HK v grafu , pak zadání TSP zkonstruovat jako , kde . Pak by aproximační algoritmus s chybou musel určitě vždy vrátit přesné řešení, takže by musel být NP-těžký.

1.2 Aproximační schémata

Definice (Aproximační schéma)

Aproximační schéma pro optimalizační úlohu je aproximační algoritmus, který má jako vstup instanci dané úlohy a číslo , a který pro libovolné pracuje jako aproximační algoritmus s relativní chybou . Doba běhu může být exponenciální jak vzhledem k – velikosti vstupní instance, tak vzhledem k .

Definice (Polynomiální aproximační schéma)

Polynomiální aproximační schéma je takové aproximační schéma, které pro každé pevné běží v polynomiálním čase vzhledem k (ale stále může být exponenciální vzhledem k .

Definice (Úplně polynomiální aproximační schéma)

Úplně polynomiální aproximační schéma je polynomiální aprox. schéma, běžící také v polynomiálním čase vzhledem k (tj. algoritmus s konstantně-krát menší relativní chybou běží v konstantně-krát delším čase).

Úplná polynomiálna aproximačná schéma pre problém batohu

Zadanie pre “dvojrozmernú variantu” problému batohu je hmotností predmetov , obmedzenie na celkovú hmotnosť a hodnoty predmetov . Úlohou je nájsť takú množinu , aby a bolo čo najväčšie.

Nech . Zadefinujme si ako najmenšia hmotnosť takej podmnožiny predmetov , ktorých celková hodnota je práve . Potom:

V treťom prípade nepridáme vec , lebo by sme prekročili cenu (spomeňme si na definíciu ), v štvrtom ju pridáme ak nám nepokazí hmotnosť.

Pomocou tohto môžeme napísať algoritmus využívajúci dynamické programovanie a ako výsledok vrátime . Tento algoritmus bude mať zložitosť , čo je iba pseudopolynomiálny algoritmus. Ten však môžeme upraviť.

Upravme si zadanie tak, že hodnoty všetkých predmetov orežeme o najnižšie bity. Ak chceme relatívnu chybu , tak orežeme bitov (nahradíme ich nulami) (prečo práve toľko bude vysvetlené nižšie). Tým sme získali novú inštanciu problému batohu, kde hmotnosti a limit sú rovnaké, ale pre každé je hodnota predmetu . Náš algoritmus bude potrebovať čas (pretože ignorujeme nulové bity na konci každej hodnoty predmetu). Riešenie , ktoré dostaneme bude možno rôzne od optima pôvodnej úlohy, ale bude platiť:

Prvá nerovnosť platí, lebo je optimum v pôvodnej úlohe, druhá lebo , tretia lebo je optimum novej úlohy, štvrtá lebo a posledná lebo . Naše riešenie je teda najviac pod optimom. Dolný odhad optima je (predpokladáme, že každý predmet sa samotný vmestí do batoha, ináč môžeme príliš ťažké predmety vyhodiť ako preprocessing). Relatívna chyba je teda

Takže pre zadané orežeme bitov a dostaneme algoritmus, ktorého relatívna chyba je a jeho časová zložitosť je , čo je polynomiálne aj v aj v , preto je to úplná polynomiálna aproximačná schéma.