A strongly polynomial simplex method for the linear fractional assignment problem

被引：11
作者：
Kabadi, Santosh N. [2 ]
Punnen, Abraham P. [1 ]
机构：
[1] Simon Fraser Univ, Dept Math, Surrey, BC V3T 0A3, Canada
[2] Univ New Brunswick, Fac Business Adm, Fredericton, NB, Canada
来源：
OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 04期
基金：
加拿大自然科学与工程研究理事会;
关键词：
assignment problem; linear fractional programming; simplex method; complexity; strongly polynomial algorithms;
D O I：
10.1016/j.orl.2007.12.001
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：402 / 407
页数：6
相关论文
共 26 条
[21]  
ROOHYLALEH, 1981, THESIS CARLETON U OT
[22]   AN ALGORITHM FOR FRACTIONAL ASSIGNMENT PROBLEMS [J].
SHIGENO, M ;
SARUWATARI, Y ;
MATSUI, T .
DISCRETE APPLIED MATHEMATICS, 1995, 56 (2-3) :333-343
[23]   A new pivot selection rule for the network simplex algorithm [J].
Sokkalingam, PT ;
Sharma, P ;
Ahuja, RK .
MATHEMATICAL PROGRAMMING, 1997, 78 (02) :149-158
[24]  
Stancu-Minasian I.M., 1997, Fractional Programming: Theory, Methods and Applications
[25]  
Swarup K., 1965, OPER RES, V10, P380
[26]  
SWARUP K, 1977, METRIKA, V15, P81
123