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%2F04%3A00003549" target="_blank" >RIV/00216208:11320/04:00003549 - 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
RANDOM EDGE is a pivot rule for the simplex algorithm, widely believed to be efficient. We construct abstract objective functions on n-dimensional cubes that force RANDOM EDGE to make exp(const.n^(1/3)) steps with high probability.
Czech name
Algoritmus RANDOM EDGE může být exponenciální na abstraktních krychlích
Czech description
RANDOM EDGE je pivotovací pravidlo pro simplexovou metodu, dosud považované za efektivní. Konstruují se abstraktní cílové funkce na krychlích, pro něž je toto pravidlo velmi pomalé.

Project
<a href="/en/project/LN00A056" target="_blank" >LN00A056: Institute of Theoretical Computer Science (Center of Young 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
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science
ISBN
0-7695-2228-9
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
92-100
Publisher name
IEEE Computer Society
Place of publication
Los Alamitos, CA
Event location
Los Alamitos, CA
Event date
Jan 1, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)