Rainer E. Burkard, Günter Rote, Günther Ruhe, and Norbert Sieber:

Algorithmische Untersuchungen zu bikriteriellen kostenminimalen Flüssen in Netzwerken

Wissenschaftliche Zeitschrift der Technischen Hochschule Leipzig 33 (1989), 333–341, (Zbl 706.90024).


Finding optimal flows in networks is one of the most common tasks in Operations Research. With few exceptions, this problem has so far been treated with a single objective function only. Many practical problems involve, however, several competing objectives.

In this paper we design and analyze algorithms for bicriteria minimum-cost flows. We present some complexity estimates, which lay the basis for the development of algorithms. We present some general results about the approximation of convex functions. We describe an exact algorithm and different realizations of the Sandwich approximation scheme, and we give results of numerical test calculations.

  pdf file (gzipped)
other papers about this subject
Last update: March 9, 2012.