About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
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.
Related
Conference paper
Competitive paging with locality of reference
Conference paper
Navigating in Unfamiliar Geometric Terrain
Conference paper