Publikace na Matematicko-fyzikální fakulta |
2006
Abstrakt
Dokazuje se, že NÁHODNÁ HRANA, což je simplexový algoritmus, který vždy vybere náhodnou zlepšující hranu, může v modelu abstraktních účelových funkcí vyžadovat exponenciálně mnoho kroků. Definuje se abstraktní účelová funkce na n-dimenzionální krychli, pro niž algoritmus, spuštěný v náhodně zvoleném vrcholu, s velkou pravděpodobností potřebuje nejméně exp(const.n^{1/3}) kroků.