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/

Zendy Plus

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

Zendy Tools

Zendy Open

It is an open question to determine if the theory of self-concordant barrierscan provide an interior point method with strongly polynomial complexity inlinear programming. In the special case of the logarithmic barrier, it wasshown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebraand Geometry, 2018] that the answer is negative. In this paper, we show thatnone of the self-concordant barrier interior point methods is stronglypolynomial. This result is obtained by establishing that, on parametricfamilies of convex optimization problems, the log-limit of the central pathdegenerates to a piecewise linear curve, independently of the choice of thebarrier function. We provide an explicit linear program that falls in the sameclass as the Klee-Minty counterexample, i.e., in dimension $n$ with $2n$constraints, in which the number of iterations is $\Omega(2^n)$.

No self-concordant barrier interior point method is strongly polynomial