An epsilon-relaxation method for separable convex cost generalized networkflow problems

We generalize the epsilon-relaxation method of [14] for the single commodit y, linear or separable convex cost network flow problem to network flow pro blems with positive gains. The method maintains epsilon-complementary slack ness at all iterations and adjusts the are flows and the node prices so as to satisfy flow conservation upon termination. Each iteration of the method involves either a price change on a node or a flow change along an are or a flow change along a simple cycle. Complexity bounds for the method are de rived. For one implementation employing epsilon-scaling, the bound is polyn omial in the number of nodes N, the number of arcs A, a certain constant Ga mma depending on the are gains, and ln(epsilon(0)/<(epsilon)over bar>), whe re epsilon(0) and <(epsilon)over bar> denote, respectively, the initial and the final tolerance epsilon.