English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Random-Facet algorithm of Kalai and of Matousek, Sharir and Welzl is anelegant randomized algorithm for solving linear programs and more generalLP-type problems. Its expected subexponential time of$2^{\tilde{O}(\sqrt{m})}$, where $m$ is the number of inequalities, makes itthe fastest known combinatorial algorithm for solving linear programs. Wepreviously showed that Random-Facet performs an expected number of$2^{\tilde{\Omega}(\sqrt[3]{m})}$ pivoting steps on some LPs with $m$inequalities that correspond to $m$-action Markov Decision Processes (MDPs). Wealso showed that Random-Facet-1P, a one permutation variant of Random-Facet,performs an expected number of $2^{\tilde{O}(\sqrt{m})}$ pivoting steps onthese examples. Here we show that the same results can be obtained using LPsthat correspond to instances of the classical shortest paths problem. Thisshows that the stochasticity of the MDPs, which is essential for obtaininglower bounds for Random-Edge, is not needed in order to obtain lower bounds forRandom-Facet. We also show that our new $2^{\tilde{\Omega}(\sqrt{m})}$ lowerbound applies to Random-Bland, a randomized variant of the classicalanti-cycling rule suggested by Bland.

Random-Facet and Random-Bland require subexponential time even for shortest paths