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

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity basedframework for solving linear programming (LP) in time depending only on theconstraint matrix in the bit complexity model. In Tardos's framework, onereduces solving the LP $\min \langle c,{x}\rangle$, $Ax=b$, $x \geq 0$, $A \in\mathbb{Z}^{m \times n}$, to solving $O(nm)$ LPs in $A$ having small integercoefficient objectives and right-hand sides using any exact LP algorithm. Thisgives rise to an LP algorithm in time poly$(n,m\log\Delta_A)$, where $\Delta_A$is the largest subdeterminant of $A$. A significant extension to the real modelof computation was given by Vavasis and Ye (Math. Prog. '96), giving aspecialized interior point method that runs in time poly$(n,m,\log\bar\chi_A)$,depending on Stewart's $\bar{\chi}_A$, a well-studied condition number.  In this work, we extend Tardos's original framework to obtain such a runningtime dependence. In particular, we replace the exact LP solves with approximateones, enabling us to directly leverage the tremendous recent algorithmicprogress for approximate linear programming. More precisely, we show that thefundamental "accuracy" needed to exactly solve any LP in $A$ is inversepolynomial in $n$ and $\log\bar{\chi}_A$. Plugging in the recent algorithm ofvan den Brand (SODA '20), our method computes an optimal primal and dualsolution using ${O}(m n^{\omega+1} \log (n)\log(\bar{\chi}_A+n))$ arithmeticoperations, outperforming the specialized interior point method of Vavasis andYe and its recent improvement by Dadush et al (STOC '20).  At a technical level, our framework combines together approximate LPsolutions to compute exact ones, making use of constructive proximity theorems-- which bound the distance between solutions of "nearby" LPs -- to keep therequired accuracy low.

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers