Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914473149726720 |
|---|---|
| author | Gribanov, Dmitry Khayaleyev, Tagir Cherniavskii, Mikhail Klimenko, Maxim Malyshev, Dmitry Moiseev, Stanislav |
| author_facet | Gribanov, Dmitry Khayaleyev, Tagir Cherniavskii, Mikhail Klimenko, Maxim Malyshev, Dmitry Moiseev, Stanislav |
| contents | We study the standard-form ILP problem $\max\{ c^\top x \colon A x = b,\; x \in Z_{\geq 0}^n \}$, where $A\in Z^{k\times n}$ has full row rank. We obtain refined FPT algorithms parameterized by $k$ and $Δ$, the maximum absolute value of a $k\times k$ minor of $A$. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let $κ_k$ denote the maximum discrepancy over all matrices with $k$ columns whose columns have Euclidean norm at most $1$. Up to polynomial factors in the input size, the optimization problem can be solved in time $O(κ_k)^{2k}Δ^2$, and the corresponding feasibility problem in time $O(κ_k)^kΔ$. Using the best currently known bound $κ_k=\widetilde O(\log^{1/4}k)$, this yields running times $O(\log k)^{\frac{k}{2}(1+o(1))}Δ^2$ and $O(\log k)^{\frac{k}{4}(1+o(1))}Δ$, respectively. Under the Komlós conjecture, the dependence on $k$ in both running times reduces to $2^{O(k)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_09806 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting Gribanov, Dmitry Khayaleyev, Tagir Cherniavskii, Mikhail Klimenko, Maxim Malyshev, Dmitry Moiseev, Stanislav Data Structures and Algorithms Computational Complexity Computational Geometry Optimization and Control We study the standard-form ILP problem $\max\{ c^\top x \colon A x = b,\; x \in Z_{\geq 0}^n \}$, where $A\in Z^{k\times n}$ has full row rank. We obtain refined FPT algorithms parameterized by $k$ and $Δ$, the maximum absolute value of a $k\times k$ minor of $A$. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let $κ_k$ denote the maximum discrepancy over all matrices with $k$ columns whose columns have Euclidean norm at most $1$. Up to polynomial factors in the input size, the optimization problem can be solved in time $O(κ_k)^{2k}Δ^2$, and the corresponding feasibility problem in time $O(κ_k)^kΔ$. Using the best currently known bound $κ_k=\widetilde O(\log^{1/4}k)$, this yields running times $O(\log k)^{\frac{k}{2}(1+o(1))}Δ^2$ and $O(\log k)^{\frac{k}{4}(1+o(1))}Δ$, respectively. Under the Komlós conjecture, the dependence on $k$ in both running times reduces to $2^{O(k)}$. |
| title | Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting |
| topic | Data Structures and Algorithms Computational Complexity Computational Geometry Optimization and Control |
| url | https://arxiv.org/abs/2604.09806 |