Matroid depth parameters and Graver bases

Integer programming (IP) represents a fundamental problem in discrete optimization, and it is of both high theoretical and practical importance. However, solving instances of integer programming is in general NP-hard, and therefore, a long line of research has been devoted to identifying classes of IP that can be solved efficiently. One of the most prominent cases is IP in fixed dimension, which can be solved in polynomial time due to the famous result of Lenstra. As for algorithms for IP in variable dimension, recent developments show that IP can be solved efficiently when the constraint matrix admits a block-like structure -- this is represented for example by the classes of n-fold, 2-stage stochastic, or multi-stage stochastic integer programming. A large family of algorithms for solving IP in variable dimension has been based on the framework of iterative augmentation. The idea of this framework is similar to computing the maximum flow on graphs -- starting with an initial feasible solution to IP, we iteratively apply improving steps until we converge to an optimal solution. The notion of Graver basis then represents the set of improving steps. However, the Graver basis of the matrix can be very large, and to avoid explicit computation, the algorithms rely on the bounds on the ℓ1 or ℓ∞-norm of the elements of the Graver basis.

In this talk, we describe the connection between the norms of the elements of the Graver basis and matroid depth parameters. In particular, we give a structural characterization of matrices with small ℓ1 -norm, and as a corollary show that IP is fixed-parameter tractable for parameterization with this notion. Moreover, we briefly discuss the connection of matroid theory to linear programming and the circuit imbalance measures.

The talk is based on the results of joint work with M. Briański, M. Koutecký, D. Kráľ, and F. Schröder.