Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143056 | Operations Research Letters | 2008 | 6 Pages |
Abstract
In this paper we show that the complexity of the simplex method for the linear fractional assignment problem (LFAP) is strongly polynomial. Although LFAP can be solved in polynomial time using various algorithms such as Newton’s method or binary search, no polynomial time bound for the simplex method for LFAP is known.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Santosh N. Kabadi, Abraham P. Punnen,