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

Let $A \in Z^{m \times n}$, $rank(A) = n$, $b \in Z^m$, and $P$ be an$n$-dimensional polyhedron, induced by the system $A x \leq b$.  It is a known fact that if $F$ is a $k$-face of $P$, then there exist atleast $n-k$ linearly independent inequalities of the system $A x \leq b$ thatbecome equalities on $F$. In other words, there exists a set of indices $J$,such that $|J| \geq n-k$, $rank(A_{J}) = n-k$, and  $$  A_{J} x - b_{J} = 0,\quad \text{for any $x \in F$}.  $$  We show that a similar fact holds for the integer polyhedron  $$  P_{I} = conv.hull\bigl(P \cap Z^n\bigr),  $$  if we additionally suppose that $P$ is $\Delta$-modular, for some $\Delta \in\{1,2,\dots\}$. More precisely, if $F$ is a $k$-face of $P_{I}$, then thereexists a set of indices $J$, such that $|J| \geq n-k$, $rank(A_{J}) = n-k$, and  $$  A_{J} x - b_{J} \overset{\Delta}{=} 0,\quad \text{for any $x \in F \capZ^n$},  $$ where $x \overset{\Delta}{=} y$ means that $\|x - y\|_{\infty} < \Delta$.In other words, there exist at least $n-k$ linearly independent inequalities ofthe system $A x \leq b$ that almost become equalities on $F \cap Z^n$. When wesay almost, we mean that the slacks are not greater than $\Delta-1$. Using thisfact, we prove the inequality  $$  |vert(P_I)| \leq 2 \cdot \binom{m}{n} \cdot \Delta^{n-1},  $$ for the number of vertices of $P_I$, which is better, than the state ofthe art bound for $\Delta = O(n^2)$.

On a Simple Connection Between $\Delta$-modular ILP and LP, and a New Bound on the Number of Integer Vertices