Accession Number : ADA323687

Title :   Newton's Method for Fractional Combinatorial Optimization,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Radzik, Thomas

PDF Url : ADA323687

Report Date : JAN 1992

Pagination or Media Count : 27

Abstract : We consider Newton's method for the linear fractional combinatorial optimization. First we show a strongly polynomial bound on the number of iterations for the general case. Then we consider the transshipment problem when the maximum arc cost is being minimized. This problem can be reduced to the maximum mean-weight cut problem, which is a special case of the linear fractional combinatorial optimization. We prove that Newton's method runs in O(m) iterations for the maximum mean weight cut problem. One iteration is dominated by the maximum flow computation, so the overall running time is O(m2n). The previous fastest algorithm is based on Meggido's parametric search method and runs in O(n3m) time.

Descriptors :   *COMBINATORIAL ANALYSIS, *NUMERICAL METHODS AND PROCEDURES, *NETWORK FLOWS, ALGORITHMS, OPTIMIZATION, PARAMETRIC ANALYSIS, POLYNOMIALS, SCALAR FUNCTIONS, ITERATIONS.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE