BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-95-19
       ENTRY:: March 20, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Fast Approximation Algorithm for Minimum Cost Multicommodity
               Flow
        TYPE:: Technical Note
      AUTHOR:: Kamath, Anil
      AUTHOR:: Palmon, Omri
      AUTHOR:: Plotkin, Serge
        DATE:: March 1995
       PAGES:: 10
    ABSTRACT:: Minimum-cost multicommodity flow problem is one of the
               classical optimization problems that arises in a variety of
               contexts. Applications range from finding optimal ways to
               route information through communication networks to VLSI
               layout.

               In this paper, we describe an efficient deterministic
               approximation algorithm, which given that there exists a
               multicommodity flow of cost $B$ that satisfies all the
               demands, produces a flow of cost at most $(1+\delta)B$ that
               satisfies $(1-\epsilon)$-fraction of each demand. For
               constant $\delta$ and $\epsilon$, our algorithm runs in
               $O^*(kmn^2)$ time, which is an improvement over the
               previously fastest (deterministic) approximation algorithm
               for this problem due to Plotkin, Shmoys, and Tardos, that
               runs in $O^*(k^2m^2)$ time.
       NOTES:: [Adminitrivia V1/Prg/19950320]
         END:: STAN//CS-TN-95-19