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

We consider integer programming problems in standard form $\max \{c^Tx : Ax =b, \, x\geq 0, \, x \in Z^n\}$ where $A \in Z^{m \times n}$, $b \in Z^m$ and $c\in Z^n$. We show that such an integer program can be solved in time $(m\Delta)^{O(m)} \cdot \|b\|_\infty^2$, where $\Delta$ is an upper bound on eachabsolute value of an entry in $A$. This improves upon the longstanding bestbound of Papadimitriou (1981) of $(m\cdot \Delta)^{O(m^2)}$, where in addition,the absolute values of the entries of $b$ also need to be bounded by $\Delta$.Our result relies on a lemma of Steinitz that states that a set of vectors in$R^m$ that is contained in the unit ball of a norm and that sum up to zero canbe ordered such that all partial sums are of norm bounded by $m$. We also usethe Steinitz lemma to show that the $\ell_1$-distance of an optimal integer andfractional solution, also under the presence of upper bounds on the variables,is bounded by $m \cdot (2\,m \cdot \Delta+1)^m$. Here $\Delta$ is again anupper bound on the absolute values of the entries of $A$. The novel strength ofour bound is that it is independent of $n$. We provide evidence for thesignificance of our bound by applying it to general knapsack problems where weobtain structural and algorithmic results that improve upon the recentliterature.

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma