- This event has passed.

# Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row

## Wednesday, July 14, 2021 @ 5:00 PM - 6:00 PM KST

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than *k* vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for *k*=0 (bipartite graphs) and for *k*=1.

We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky.