RANDOM EDGE can be exponential on abstract cubes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00002728" target="_blank" >RIV/00216208:11320/06:00002728 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
RANDOM EDGE can be exponential on abstract cubes
Original language description
We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions. We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const.n^{1/3}) steps with high probability.
Czech name
NÁHODNÁ HRANA může být na abstraktních krychlích exponenciální
Czech description
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ů.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BD - Information theory
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)