A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming

on YouTube ↗32m

" summary

Proves a strongly polynomial algorithm for integer programs whose constraint matrix has all minors in {−2,−1,0,1,2} (bimodular). Key steps: solve the LP, restrict to the tight cone at a fractional vertex, perform an affine change of variables that yields a parity-constrained TU reduction, and apply a structured Seymour-style decomposition into network/transpose/2×2 blocks. Uses combinatorial submodular/capacitated procedures on base blocks, runs in strongly polynomial time, and yields new polynomial algorithms for problems like maximum-weight independent set when the odd-cycle packing number equals one.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:43Toward general classes of efficiently solvable ILPs
3. 2:41Beyond TU-ness: Bimodular integer programs
4. 10:16Our approach on a high level
5. 12:40Prior work by Veselov and Chirkov (2009)
6. 17:35Seymour's TU decomposition (1)
7. 20:50Using Seymour's decomposition to solve CPTU
8. 27:49Conclusions