The fixed--modular integer programming tractability conjecture
The fixed--modular integer programming tractability conjecture
Let be fixed. An integer program of the form (IP) has a constraint matrix that is -modular if its full-rank minors have absolute value at most and at least one has absolute value .
Fixed- tractability conjecture. There is a polynomial-time algorithm to solve any integer program of the form (IP) with a -modular constraint matrix.
This conjecture extends the polynomial-time solvability of totally unimodular integer programs to every fixed bound on the maximal non-vanishing subdeterminants. Its status is not resolved in the supplied text.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Björn Kriepke, Gohar M. Kyureghyan and Matthias Schymura, “On the size of integer programs with bounded non-vanishing subdeterminants”, arXiv:2309.03772 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.