Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined $2^{O(k)}$-analysis)
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 $\ell_2$-discrepancy bounds in Komlós' setting. Up to polynomial factors in the input size, the optimization problem can be solved in time $2^{O(k)}Δ^2$, and the corresponding feasibility problem in time $2^{O(k)}Δ$. We would like to point out that the original…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.09806
curl -X POST /api/v1/records/arxiv/2604.09806/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.09806/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'