Authors

Citation

P. Tseng et Dp. Bertsekas, An epsilon-relaxation method for separable convex cost generalized networkflow problems, MATH PROGR, 88(1), 2000, pp. 85-104

Citations number

34

Language

INGLESE

art.tipo

Article

Categorie Soggetti

Mathematics

Journal title

MATHEMATICAL PROGRAMMING

ISSN journal

0025-5610
→ ACNP

Volume

88

Issue

1

Year of publication

2000

Pages

85 - 104

Database

ISI

SICI code

0025-5610(200006)88:1<85:AEMFSC>2.0.ZU;2-S

Abstract

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.