2024/11/22 by Kober, Stefan · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2411.15282
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 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables.