Speeding-up linear programming using fast matrix multiplication
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 332-337
- https://doi.org/10.1109/sfcs.1989.63499
Abstract
The author presents an algorithm for solving linear programming problems that requires O((m+n)/sup 1.5/nL) arithmetic operations in the worst case, where m is the number of constraints, n the number of variables, and L a parameter defined in the paper. This result improves on the best known time complexity for linear programming by about square root n. A key ingredient in obtaining the speedup is a proper combination and balancing of precomputation of certain matrices by fast matrix multiplication and low-rank incremental updating of inverses of other matrices. Specializing the algorithm to problems such as minimum-cost flow, flow with losses and gains, and multicommodity flow leads to algorithms whose time complexity closely matches or is better than the time complexity of the best known algorithms for these problems.<>Keywords
This publication has 10 references indexed in Scilit:
- The toric ℎ-vectors of partially ordered setsTransactions of the American Mathematical Society, 2000
- Speeding up Karmarkar's algorithm for multicommodity flowsMathematical Programming, 1996
- A polynomial-time algorithm, based on Newton's method, for linear programmingMathematical Programming, 1988
- Combinatorial algorithms for the generalized circulation problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Solving minimum-cost flow problems by successive approximationPublished by Association for Computing Machinery (ACM) ,1987
- Matrix multiplication via arithmetic progressionsPublished by Association for Computing Machinery (ACM) ,1987
- Fast algorithms for convex quadratic programming and multicommodity flowsPublished by Association for Computing Machinery (ACM) ,1986
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- How to Multiply Matrices FasterLecture Notes in Computer Science, 1984
- Systems of distinct representatives and linear algebraJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967