|
|||||
|
|
A strongly polynomial simplex method for the linear fractional assignment problem |
|
| Authors: | Santosh N. Kabadi Abraham P. Punnen |
| Affiliation: | aFaculty of Business Administration, University of New Brunswick, Fredericton, New Brunswick, Canada;bDepartment of Mathematics, Simon Fraser University Surrey, Central City, 250-13450 102nd AV, Surrey, British Columbia,V3T 0A3, Canada |
| 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. |
| Keywords: | Assignment problem Linear fractional programming Simplex method Complexity Strongly polynomial algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |