|
Combinatorial optimization with rational objective functions: A communication R.K. Ahuja, J.L. Batra, and S.K. Gupta, Mathematics of Operations Research 8, 314, 1983 This article focuses on a proposed algorithm to solve a class of combinatorial optimization problems with rational objective functions in polynomial time. N. Megiddo, mathematician has proposed an algorithm to solve a class of combinatorial optimization problems with rational objective functions in polynomial time. The minimum ratio path problem is claimed to be one such problem. The essential problem that Megiddo's algorithm faces for the minimum ratio path problem is the presence of negative cycles. If the network contains cycles, then while solving the shortest path problem a negative cycle in the network was found. |