aussois_header.png

Totally Δ-modular IPs with two non-zeros in most rows
Stefan Kober  1@  
1 : Université Libre de Bruxelles

Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge & Yuditsky (J. ACM 2024) by allowing for additional, unifying constraints and variables.


Personnes connectées : 2 Vie privée | Accessibilité
Chargement...