We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is

We prove our result by associating a
*lattice* to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of near-shortest vectors in it is polynomially bounded.
The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of near-shortest circuits in a regular matroid.
This is the technical core of the paper and relies on Seymour's decomposition theorem for regular matroids.
It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids.
Both of our results, on lattices and matroids, should be of independent interest.