Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909648731242496 |
|---|---|
| author | Cherniavskii, M. Gribanov, D. Malyshev, D. Pardalos, P. M. |
| author_facet | Cherniavskii, M. Gribanov, D. Malyshev, D. Pardalos, P. M. |
| contents | For integers $k,n \geq 0$ and a cost vector $c \in Z^n$, we study two fundamental integer linear programming (ILP) problems: \[
\text{(Standard Form)} \quad \max\bigl\{c^\top x \colon Ax = b,\ x \in Z^n_{\geq 0}\bigr\} \text{ with } A \in Z^{k \times n}, \text{rank}(A) = k, b \in Z^k, \] \[
\text{(Canonical Form)} \quad \max\bigl\{c^\top x \colon Ax \leq b,\ x \in Z^n\bigr\} \text{ with } A \in Z^{(n+k) \times n}, \text{rank}(A) = n, b \in Z^{n+k}. \] We present improved algorithms for both problems and their feasibility versions, parameterized by $k$ and $Δ$, where $Δ$ denotes the maximum absolute value of $\text{rank}(A) \times \text{rank}(A)$ subdeterminants of $A$. Our main complexity results, stated in terms of required arithmetic operations, are: \[ \text{Optimization:}\quad O(\log k)^{2k} \cdot Δ^2 / 2^{Ω(\sqrt{\log Δ})} + 2^{O(k)} \cdot \text{poly}(φ), \] \[ \text{Feasibility:} \quad O(\log k)^k \cdot Δ\cdot (\log Δ)^3 + 2^{O(k)} \cdot \text{poly}(φ), \] where $φ$ represents the input size measured by the bit-encoding length of $(A,b,c)$. We also examine several special cases when $k \in \{0,1\}$, which have important applications in: expected computational complexity of ILP with varying right-hand side $b$, ILP problems with generic constraint matrices, ILP problems on simplices. Our results yield improved complexity bounds for these specific scenarios.
As independent contributions, we present: An $n^2/2^{Ω(\sqrt{\log n})}$-time algorithm for the tropical convolution problem on sequences indexed by elements of a finite Abelian group of order $n$; A complete and self-contained error analysis of the generalized DFT over Abelian groups in the Word-RAM model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17001 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version) Cherniavskii, M. Gribanov, D. Malyshev, D. Pardalos, P. M. Computational Complexity Data Structures and Algorithms Commutative Algebra Optimization and Control For integers $k,n \geq 0$ and a cost vector $c \in Z^n$, we study two fundamental integer linear programming (ILP) problems: \[ \text{(Standard Form)} \quad \max\bigl\{c^\top x \colon Ax = b,\ x \in Z^n_{\geq 0}\bigr\} \text{ with } A \in Z^{k \times n}, \text{rank}(A) = k, b \in Z^k, \] \[ \text{(Canonical Form)} \quad \max\bigl\{c^\top x \colon Ax \leq b,\ x \in Z^n\bigr\} \text{ with } A \in Z^{(n+k) \times n}, \text{rank}(A) = n, b \in Z^{n+k}. \] We present improved algorithms for both problems and their feasibility versions, parameterized by $k$ and $Δ$, where $Δ$ denotes the maximum absolute value of $\text{rank}(A) \times \text{rank}(A)$ subdeterminants of $A$. Our main complexity results, stated in terms of required arithmetic operations, are: \[ \text{Optimization:}\quad O(\log k)^{2k} \cdot Δ^2 / 2^{Ω(\sqrt{\log Δ})} + 2^{O(k)} \cdot \text{poly}(φ), \] \[ \text{Feasibility:} \quad O(\log k)^k \cdot Δ\cdot (\log Δ)^3 + 2^{O(k)} \cdot \text{poly}(φ), \] where $φ$ represents the input size measured by the bit-encoding length of $(A,b,c)$. We also examine several special cases when $k \in \{0,1\}$, which have important applications in: expected computational complexity of ILP with varying right-hand side $b$, ILP problems with generic constraint matrices, ILP problems on simplices. Our results yield improved complexity bounds for these specific scenarios. As independent contributions, we present: An $n^2/2^{Ω(\sqrt{\log n})}$-time algorithm for the tropical convolution problem on sequences indexed by elements of a finite Abelian group of order $n$; A complete and self-contained error analysis of the generalized DFT over Abelian groups in the Word-RAM model. |
| title | Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version) |
| topic | Computational Complexity Data Structures and Algorithms Commutative Algebra Optimization and Control |
| url | https://arxiv.org/abs/2405.17001 |