Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row
Room B232 IBS (기초과학연구원)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 …