Project in mathematics developed at the Chair of Discrete Optimization at the École Polytechnique Fédérale de Lausanne, Switzerland.
- Project director: Friedrich Eisenbrand
- Project supervisor: Jana Cslovjecsek
The final result of the project can be accessed here: Graver_bases.pdf
In the project we study the latest techniques based on the Graver bases and its bounds as well as their application to the N-Fold IP, a restricted formulation of the IP which has won relevance in the last decades given its theoretical properties and its wide applications. For the N-Fold IP we introduce the best algorithm known for its resolution running in a roughly linear time as well as a quadratic augmentation algorithm based on the properties of the Graver basis of the N-Fold matrix.
The following presentations may be useful as an overview:
- Graver, On the foundations of linear and integer linear programming I, 1975.
- Sturmfels, Algebraic Recipes for Integer Programming, 2003.
- Finhold, Hemmecke, Lower bounds on the Graver complexity of M-fold matrices, 2013.
- Eisenbrand, Hunkenschröder, Klein,Faster Algorithms for Integer Programs with Block Structure, 2018.
- Cslovjecsek, Eisenbrand, Weismantel, N-fold integer programming via LP rounding, 2020.
- Hemmecke, Onn, Romanchuk, N-fold integer programming in cubic time, 2011.
- Eisenbrand, Weismantel, Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma, 2019.
- De Loera, Hemmecke, Onn, Weismantel, N-Fold integer programming, 2006.
- Hemmecke, Exploiting Symmetries in the Computation of Graver Bases, 2004.
- Hemmecke, Onn, Weismantel, A polynomial oracle-time algorithm for convex integer minimization, 2009.
- Onn, Convex discrete optimization, 2007.
- Onn, Nonlinear discrete optimization, 2010.
- De Loera, Onn, All linear and integer programs are slim 3-way transportation programs, 2006.
- Steinitz, Bedingt konvergente reihen und konvexe systeme, 1913.