Block-structured integer programming: Can we parameterize without the largest coefficient?
Discrete Optimization · 2022-11 · 46 · 100743
DOI: 10.1016/j.disopt.2022.100743 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Optimization, 2022-11. Verfasst von Hua Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 35 Literaturangaben. Gefördert von: NSF CCF, National Natural Science Foundation of China.
Abstract (Originalsprache)
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 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 $\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$ and the 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 IP can 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 integer programming), then it can be solved in linear time $n\cdot poly(t_A,\log \Delta)$.
Förderung
- NSF CCF
- National Natural Science Foundation of China
Zitieren
APA
Chen, H., Chen, L., & Zhang, G. (2022). Block-structured integer programming: Can we parameterize without the largest coefficient?. Discrete Optimization, 46, 100743. https://doi.org/10.1016/j.disopt.2022.100743
Vancouver
Chen H, Chen L, Zhang G. Block-structured integer programming: Can we parameterize without the largest coefficient?. Discrete Optimization. 2022;46:100743. doi:10.1016/j.disopt.2022.100743
BibTeX
@article{Chen2022,
author = {Chen, Hua and Chen, Lin and Zhang, Guochuan},
title = {Block-structured integer programming: Can we parameterize without the largest coefficient?},
journal = {Discrete Optimization},
year = {2022},
volume = {46},
pages = {100743},
doi = {10.1016/j.disopt.2022.100743}
}
EUVIMED