Network Optimization – Page 31 – Optimization Online

On the min-cut max-flow ratio for multicommodity flows

Published: 2001/02/05

In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems. We use a so-called aggregated commodity formulation and an optimal solution to its dual to show our main result. Currently, the best known bound for this ratio is proportional to log(k) where k is the number of origin-destination … Read more

Newton Algorithms for Large-Scale Strictly Convex Separable Network Optimization

Published: 2001/01/19

Aleksandar Donev

Phillip Duxbury

In this work we summarize the basic elements of primal and dual Newton algorithms for network optimization with continuously differentiable (strictly) convex arc cost functions. Both the basic mathematics and implementation are discussed, and hints to important tuning details are made. The exposition assumes that the reader posseses a significant level of prior knowledge in … Read more