AN ALGORITHM FOR FRACTIONAL ASSIGNMENT PROBLEMS

In this paper, we propose a polynomial-time algorithm for fractional a ssignment problems. The fractional assignment problem is interpreted a s follows. Let G=(I,J,E) be a bipartite graph where I and J are vertex sets and E subset of or equal to I x J is an edge set. We call an edg e subset X( subset of or equal to E) an assignment if every vertex is incident to exactly one edge from X. Given an integer weight c(ij) and a positive integer weight d(ij) for every edge (i,j) is an element of E, the fractional assignment problem finds an assignment X( subset of or equal to E) such that the ratio (Sigma(i,j) is an element of X) C- ij)/(Sigma((i,j) is an element of X d(ij)) is minimized. Some algorith ms were developed for the fractional assignment problem. Recently, Rad zik (1992) showed that an algorithm which is based on the parametric a pproach and Newton's method is the fastest one among them. Actually, i t solves the fractional assignment problem in O(root nm log(2)(nCD)/(1 + log log(nCD)- log log(nD))) time where \I\ = \J\ = n, \E\ = m, C = max {1, max {\c(ij)\ :(i,j) is an element of E}} and D = max {d(ij):(i ,j) is an element of E} + 1. Our algorithm developed in this paper is also based on the parametric approach, but it is combined with the app roximate binary search method. The time complexity of our algorithm is O(root nm log D log(nCD)) time, and provides with a better time bound than the above algorithm.