BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-95-20
       ENTRY:: March 20, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Interior Point Algorithms for Exact and Approximate Solution
               of Multicommodity Flow Problems
        TYPE:: Technical Note
      AUTHOR:: Kamath, Anil
      AUTHOR:: Palmon, Omri
        DATE:: March 1995
       PAGES:: 20
    ABSTRACT:: 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.
       NOTES:: [Adminitrivia V1/Prg/19950320]
         END:: STAN//CS-TN-95-20