The polynomial-time solvability conjecture for totally -modular integer programs
The polynomial-time solvability conjecture for totally -modular integer programs
Let be a totally -modular matrix, meaning that every square submatrix of has determinant bounded by in absolute value. For integer vectors and integer variable vector , consider the integer program
Totally -modular integer-program conjecture. For any constant , this integer program can be solved in polynomial time when is totally -modular.
The case is the totally unimodular case. Artmann, Weismantel, and Zenklusen answered the conjecture affirmatively for , while the cases remain open.
Sources & referencesView supporting material
Primary source
Caleb McFarland, “Totally Δ-Modular Tree Decompositions of Graphic Matrices for Integer Programming”, arXiv:2602.01499 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.