An algorithm for fractional assignment problems

In this paper the authors propose a polynomial-time algorithm for fractional assignment problems. The fractional assignment problem is interpreted as follows. Let G=(I, J, E) be a bipartite graph where I and J are vertex sets and EIJ is an edge set. The authors call an edge subset X(E) an assignment if every vertex is incident to exactly one edge from X. Given an integer weight ci j and a positive integer weight d i j for every edge (i, j). E, the fractional assignment problem finds an assignment ((E) such that the ratio is minimized. Some algorithms were developed for the fractional assignment problem. Recently, Radzik showed that an algorithm which is based on the parametric approach and Newton's method is the fastest one among them. Actually, it solves the fractional assignment problem in time where . The algorithm developed in this paper is also based on the parametric approach, but it is combined with the approximate binary search method. The time complexity of the algorithm is time, and provides with a better time bound than the above algorithm.