Tesis

MATHEMATICS OF OPERATIONS RESEARCH Vol. 4. No. 4. November 1979 Printed in U S A .

COMBINATORIAL OPTIMIZATION WITH RATIONAL OBJECTIVE FUNCTIONS*
NIMROD MEGIDDO
Tel Auiu University

Let A be the problem of minimizing c l x l + . . . + c,x, subject to certain constraints on x = ( x , , . . , x,), and let B be the problem of minimizing ( a , + a , x l + . . . + o,,x,)/(b, + b , x , + . . . +b,x,) 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, maximumratio 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 generalarguments log1 presented in this paper. Algorithms of time-complexity O(IEJ . IvJ2. VJ) for a minimum ratio cycle and O(IE1. log21VJ .log IoglVI) for a minimum ratio spanning tree are developed.

.

1. Introduction. Numerous combinatorial optimization problems can be formulated as linear minimization problems subject to certain constraints. Let us denote Problem A: Minimize c , x , + . . . +cnxn s.t. x = (xl, . . . , x,,) E D.

As examples we might mention the problems of the shortest (simple) path, the minimum spanning tree, the maximum weighted matching, the minimum cut, the traveling salesman, the Chinese postman, and a variety of scheduling problems. In view of the examples given above, the following generalization of A is interesting both from the applicative and thetheoretical aspects. We denote Problem B: Minimize s.t.
(a,, + a,xl

+ . . . + a,,x,)/(b, + blxl + . . . + bnx,,)

XED

(assuming the denominator is always positive). One example of a practical ratio minimization is that of minimizing cost-to-time ratio. Dantzig, Blattner and Rao [ 5 ] and Lawler [8] introduced the problem of the minimum cost-to-time ratio cycle in a graph. This problem applies tofinding optimal ship routing. Our general result in this paper relates the time complexity of problem B to that of problem A. It turns out that whenever A has a good algorithm, then the same is true for B. An algorithm for the minimum ratio cycle problem is given by Lawler 19, Chapter 3, $131. The time bound for Lawler's algorithm depends on the numerical values of
Received November 18, 1977;revised October 20, 1978. AMS 1970 subjecr classificalion. Primary 90C30. Secondary W 3 5 . IAOR I973 subject classification. Main: Fractional programming. Cross reference: Network programming. O R / M S Index 1978 subject classification. Primary: 623 Programming, fractional. Secondary: 481 Networks/graphs; 652 ~ r o ~ r a m m i kquiva~ence/transfomations. n~, Key worh. Fractional programming,computational complexity, polynomial running time; minimum-ratio cycles, spanning trees, paths, weighted matchings.
414

0364-765X/79/04OQ/O414$01.25
Copyr~ght 1979, The Institute of Management Sc~ences 0

the parameters, namely, "the number of computational steps is bounded by a polynomial function in the number of bits required to specify an instance of the problem." The theorem proved in thepresent paper provides improved algorithms, in the sense that the time bound is a polynomial function in the number of the variables and does not depend on the numerical values of the parameters. Karp [7] solves the minimum cycle mean problem (i.e., the special case of the minimum cost-to-time ratio cycle, when all times bVare equal) in time O(I E I . / VI), where E is the edge set and V is the...