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

We consider 4-block $n$-fold integer programming, which can be written as$\max\{w\cdot x: H x=b, l\le x\le u, x\in \mathbb{Z}^{N} \}$ where theconstraint matrix $H$ is composed of small submatrices $A,B,C,D$ such that thefirst row of $H$ is $(C,D,D,\cdots,D)$, the first column of $H$ is$(C,B,B,\cdots,B)$, the main diagonal of $H$ is $(C,A,A,\cdots,A)$, and all theother entries are $0$. The special case where $B=C=0$ is known as $n$-foldinteger programming.  Prior algorithmic results for 4-block $n$-fold integer programming and itsspecial cases usually take $\Delta$, the largest absolute value among entriesof $H$ as part of the parameters. In this paper, we explore the possibility ofgetting rid of $\Delta$ from parameters, i.e., we are looking for algorithmsthat runs polynomially in $\log\Delta$. We show that, assuming $\text{P}\neq\text{NP}$, this is not possible even if $A=(1,1,\Delta)$ and $B=C=0$. However,this becomes possible if $A=(1,1,\cdots,1)$ or $A\in \mathbb{Z}^{1\times 2}$,or more generally if $A\in\mathbb{Z}^{s_A\times t_A} $ where $t_A=s_A+1$ andthe rank of matrix $A$ satisfies that $\text{rank}(A)=s_A$. More precisely,  1. If $A=(1,\ldots,1)\in \mathbb{Z}^{1\times t_A} $, then 4-block $n$-fold IPcan be solved in $(t_A+t_B)^{O(t_A+t_B)}\cdot poly(n,\log\Delta)$ time.  2. If $A\in\mathbb{Z}^{s_A\times t_A} $, $t_A=s_A+1$ and$\text{rank}(A)=s_A$, then 4-block $n$-fold IP can be solved in$(t_A+t_B)^{O(t_A+t_B)}\cdot n^{O(t_A)}\cdot poly(\log\Delta)$ time;Specifically, if in addition we have $B=C=0$ (i.e., $n$-fold integerprogramming), then it can be solved in linear time $n\cdot poly(t_A,\log\Delta)$.

Block-structured Integer Programming: Can we Parameterize without the Largest Coefficient?