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

DOI10.1016/J.DISOPT.2022.100743MaRDI QIDQ6353064arXivFDO

Authors Hua Chen, Lin Chen, Guochuan Zhang

Publication date 5 November 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISOPT.2022.100743

Mathematics Subject Classification ID

Integer programming (90C10)

arXiv classification

math.OC

Abstract: We consider 4-block $n$-fold integer programming, which can be written as $maxwcdotx:Hx=b,llexleu,xinmathbb{Z}^N$ where the constraint matrix $H$ is composed of small submatrices $A,B,C,D$ such that the first 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 the other entries are $0$. The special case where $B=C=0$ is known as $n$-fold integer programming. Prior algorithmic results for 4-block $n$-fold integer programming and its special cases usually take $Delta$, the largest absolute value among entries of $H$ as part of the parameters. In this paper, we explore the possibility of getting rid of $Delta$ from parameters, i.e., we are looking for algorithms that runs polynomially in $logDelta$. We show that, assuming $extPeqextNP$, 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 $Ainmathbb{Z}^{1imes2}$, or more generally if $Ainmathbb{Z}^{s_{A}imes{t}_A}$ where $t_A=s_A+1$ and the rank of matrix $A$ satisfies that $extrank(A)=s_A$. More precisely, 1. If $A=(1,ldots,1)inmathbb{Z}^{1imes{t}_A}$, then 4-block $n$-fold IP can be solved in $(t_A+t_B{)}^{O(t_A+t_B)}cdotpoly(n,logDelta)$ time. 2. If $Ainmathbb{Z}^{s_{A}imes{t}_A}$, $t_A=s_A+1$ and $extrank(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)}cdotpoly(logDelta)$ time; Specifically, if in addition we have $B=C=0$ (i.e., $n$-fold integer programming), then it can be solved in linear time $ncdotpoly(t_A,logDelta)$.

This page was built for publication: Block-structured Integer Programming: Can we Parameterize without the Largest Coefficient?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6353064)