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

Following the breakthrough work of Tardos in the bit-complexity model,Vavasis and Ye gave the first exact algorithm for linear programming in thereal model of computation with running time depending only on the constraintmatrix. For solving a linear program (LP) $\max\, c^\top x,\: Ax = b,\: x \geq0,\: A \in \mathbb{R}^{m \times n}$, Vavasis and Ye developed a primal-dualinterior point method using a 'layered least squares' (LLS) step, and showedthat $O(n^{3.5} \log (\bar{\chi}_A+n))$ iterations suffice to solve (LP)exactly, where $\bar{\chi}_A$ is a condition measure controlling the size ofsolutions to linear systems related to $A$.  Monteiro and Tsuchiya, noting that the central path is invariant underrescalings of the columns of $A$ and $c$, asked whether there exists an LPalgorithm depending instead on the measure $\bar{\chi}^*_A$, defined as theminimum $\bar{\chi}_{AD}$ value achievable by a column rescaling $AD$ of $A$,and gave strong evidence that this should be the case. We resolve this openquestion affirmatively.  Our first main contribution is an $O(m^2 n^2 + n^3)$ time algorithm whichworks on the linear matroid of $A$ to compute a nearly optimal diagonalrescaling $D$ satisfying $\bar{\chi}_{AD} \leq n(\bar{\chi}^*)^3$. Thisalgorithm also allows us to approximate the value of $\bar{\chi}_A$ up to afactor $n (\bar{\chi}^*)^2$. As our second main contribution, we develop ascaling invariant LLS algorithm, together with a refined potential functionbased analysis for LLS algorithms in general. With this analysis, we derive animproved $O(n^{2.5} \log n\log (\bar{\chi}^*_A+n))$ iteration bound foroptimally solving (LP) using our algorithm. The same argument also yields afactor $n/\log n$ improvement on the iteration complexity bound of the originalVavasis-Ye algorithm.

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix