A polynomial-time test for total dual integrality in fixed dimension

DOI10.1007/BFb0121008zbMath0557.90071MaRDI QIDQ3221757

László Lovász, William Cook, Alexander Schrijver

Publication date: 1984

Published in: Mathematical Programming Studies (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmHilbert basissystem of linear inequalitiestotal dual integrality test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Linear inequalities of matrices (15A39)

Related Items

On box totally dual integral polyhedra, Testing additive integrality gaps, Alternatives for testing total dual integrality, Non total-unimodularity neutralized simplicial complexes, The complexity of recognizing linear systems with certain integrality properties, Total dual integrality of the linear complementarity problem, Recognizing conic TDI systems is hard, Integral infeasibility and testing total dual integrality