1995 · 28 citations · 13 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationApproximation AlgorithmsCombinatorial OptimizationLinear ProgrammingNetwork Flow AlgorithmsNetwork FlowsComplexityInterior-point Methods For FlowMinimum Cost FlowMulti-commodity FlowMulticommodity FlowNetwork Flow ProblemsPolynomial OptimizationQuadratic Optimization
In this paper, we present a new interior-point based polynomial algorithm for the multicommodity flow problem and its variants. Unlike all previously known interior point algorithms for multicommodity flow that have the same complexity for approximate and exact solutions, our algorithm improves running time in the approximate case by a polynomial factor. For many cases, the exact bounds are better as well. Instead of using the conventional linear programming formulation for the multicommodity flow problem, we model it as a quadratic optimization problem which is solved using interior-point techniques. This formulation allows us to exploit the underlying structure of the problem and to solve it efficiently. The algorithm is also shown to have improved stability properties. The improved complexity results extend to minimum cost multicommodity flow, concurrent flow and generalized flow problems. 1 Introduction The multicommodity flow problem is the problem of finding several network flo...
13
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · COMBINATORICA · 1984 · 4.8K citations
The maximum concurrent flow problem
Farhad Shahrokhi, David W. Matula · Journal of the ACM · 1990 · 437 citations · Full text
Natural Sciences, Computer Engineering, Computer Science +17
T. C. Hu · Operations Research · 1963 · 393 citations
Speeding-up linear programming using fast matrix multiplication
Pravin M. Vaidya · 1989 · 312 citations