Aproximační algoritmy

Aproximační algoritmy je druh algoritmů používaných při řešení optimalizačního problému, kdy nehledáme nutně optimální řešení, ale spokojíme se i s řešením, které je optimálnímu velmi blízké.

k-aproximační algoritmus

Definice

Říkáme, že algoritmus $A$ problému maximalizace kriteriální funkce $F$ je k-aproximační, jestliže existuje číslo $k\geq1$ takové, že pro všechny instance $I$ daného problému platí $F^A(I)\geq\frac{1}{k}F^{opt}(I)$ (analogicky věta platí pro algoritmy minimalizace kriteriální funkce).

Zjednodušeně řečeno: k-aproximační algoritmus optimalizačního problému nalezne vždy řešení, které je nejhůře k-krát horší než řešení optimální.

Příklady

Úrovňový algoritmus