Abstract
Recent years have seen tremendous progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow and general Linear Programs (LP). Progress on strongly polynomial solvers for combinatorial LP on the other hand has stalled. For combinatorial LP beyond directed graphs this gap between exact and high-accuracy solvers is currently quadratic. We finally break the quadratic gap and design a strongly polynomial interior-point-method for combinatorial LP, which reduces the gap to only a linear factor.