Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
4-Block Integer Programming is in FPT
Martin Koutecký, Alexandra Lassota, Koen Ligthart
Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the most important, unresolved…
cs.CC2024
Tight Lower Bounds for Block-Structured Integer Programs
Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký +2
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few…