Improved algorithms for linear inequalities with two variables per inequality

Abstract

We show that a system of m linear inequalities wit h n variables, where each inequality involves at most two variables, can be solved det erministically in O(mn log m + mnz log2 n) time. A randomized O(n3 log n + mn log3 n log m + mn log5 n) time algorithm is given for the case where in every inequality the two nonzero coefficients have opposite signs (monotone systems). This algorithm improves the known time bounds for the incapacitated generalized transshipment problem, with many sources and no sinks. We also present a new algorithm that solves the capacitated generalized flow problem by iteratively solving monotone systems. Combined with the improved bound, it yields the fastest known algorithm for the problem which does not rely on the theoretically fast matrix multiplication algorithms. This approach also yields the first strongly polynomial time bound for approximating the maximum generalized flow within any constant factor.