Linear and Integer Programming with Bounded Sub-Determinants


Swiss National Science Foundation (SNSF)


Friedrich Eisenbrand

Alfonso Cevallos


The project deals with with integer and linear programming problems where the sub-determinants of the constraint matrix are bounded by a constant. Our guiding questions will be: Is there a randomized or deterministic variant of the simplex algorithm that runs in polynomial time? How hard is integer programming under the above cicrumstance? In particular, what are the potentials and limits of approximation algorithms for packing and covering integer programs?

Selected publications