abstract
-
While the algorithmic complexity is in general worse than the one of Tardos' original algorithms, the authors, motivated by the practicality of such methods, recently proposed a simplex-based variant that is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate. In this paper, we introduce a slight modification that circumvents the determination of the largest sub-determinant while keeping the same theoretical performance. Assuming that the coefficient matrix is integer-valued and the auxiliary problems are non-degenerate, the proposed algorithm is polynomial in the dimension of the input data and the largest absolute value of a sub-determinant of the coefficient matrix.