{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia53dolvpmpsw2rggl3po32roqzixs3rjfptccfq6tplcxrcoay3e",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjivznwwisf2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.09806v1",
  "publishedAt": "2026-04-14T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Dmitry Gribanov",
    "Tagir Khayaleev",
    "Mikhail Cherniavskii",
    "Maxim Klimenko",
    "Dmitry Malyshev",
    "Stanislav Moiseev"
  ],
  "textContent": "**Authors:** Dmitry Gribanov, Tagir Khayaleev, Mikhail Cherniavskii, Maxim Klimenko, Dmitry Malyshev, Stanislav Moiseev\n\nWe 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"
}