Combinatorial Optimization with Rational Objective Functions

Let A be the problem of minimizing c 1 , x 1 , + ⋯ + c n x n subject to certain constraints on x = (x 1 , …, x n ), and let B be the problem of minimizing (a 0 + a 1 x 1 + ⋯ + a n x n )/(b 0 + b 1 x 1 + ⋯ + b n x n ) subject to the same constraints, assuming the denominator is always positive. It is shown that if A is solvable within O[p(n)] comparisons and O[q(n)] additions, then B is solvable in time O[p(n)(q(n) + p(n))]. This applies to most of the “network” algorithms. Consequently, minimum ratio cycles, minimum ratio spanning trees, minimum ratio (simple) paths, maximum ratio weighted matchings, etc., can be computed withing polynomial-time in the number of variables. This improves a result of E. L. Lawler, namely, that a minimum ratio cycle can be computed within a time bound which is polynomial in the number of bits required to specify an instance of the problem. A recent result on minimum ratio spanning trees by R. Chandrasekaran is also improved by the general arguments presented in this paper. Algorithms of time-complexity O(|E| · |V| 2 · log|V|) for a minimum ratio cycle and O(|E| · log 2 |V| · log log |V|) for a minimum ratio spanning tree are developed.