Accession Number : ADA317237

Title :   Experimental Evaluation of the Push-Relabel Method for the Minimum-Cost Flow Problem (Extended Abstract),

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Goldberg, Andrew V. ; Kharitonov, Michael

PDF Url : ADA317237

Report Date : AUG 1991

Pagination or Media Count : 12

Abstract : The generalized cost-scaling method is theoretically superior to other methods for solving the minimum-cost flow problem, in the sense that it leads to the best running time bounds currently known under the assumption that the absolute values of costs are not too big. There is some evidence that the method should perform well in practice as well: an earlier cost-scaling algorithm of Blend and Jensen was shown to be competitive with a well-established network simplex code. The method is very flexible and has many variants. Which version of the method works best in practice? But how good is the method in practice? These are the questions addressed in our study. Generalized cost scaling framework can accommodate several very different algorithms, such as the push-relabel method, the blocking flow method, multiple scaling algorithms, and cycle-canceling algorithms. We restrict our study only to push-relabel variant of the cost-scaling approach. This variant is the most promising since, in the context of the closely related maximum flow problem, several researchers reported its superior performance compared to other popular techniques. For this reason we believe that the experimental study of the push-relabel variants of the method should be done first, and in this study restrict ourself to these variants.

Descriptors :   *ALGORITHMS, *COST EFFECTIVENESS, OPTIMIZATION, QUEUEING THEORY, LOW COSTS, INPUT OUTPUT PROCESSING, HEURISTIC METHODS, SYSTEMS ANALYSIS.

Subject Categories : Computer Programming and Software
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE