.png){kind=icon}
Return
Combinatorial Optimization with Rational Objective Functions
.png){kind=icon}
PRE
AI
DOI：10.1287/moor.4.4.414.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Let A be the problem of minimizing c1, x1, + ⋯ + cnxn subject to certain constraints on x = (x1, …, xn), and let B be the problem of minimizing (a0 + a1x1 + ⋯ + anxn)/(b0 + b1x1 + ⋯ + bnxn) 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| · log2|V| · log log |V|) for a minimum ratio spanning tree are developed.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
No journal information available
Organization
No organization information available
Cited Papers
No cited papers available