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 条

[1] THE SCALING NETWORK SIMPLEX ALGORITHM [J].

AHUJA, RK ;

ORLIN, JB .

OPERATIONS RESEARCH, 1992, 40 :S5-S13

[2] A network simplex algorithm with O(n) consecutive degenerate pivots [J].

Ahuja, RK ;

Orlin, JB ;

Sharma, P ;

Sokkalingam, PT .

OPERATIONS RESEARCH LETTERS, 2002, 30 (03) :141-148

[3]

Ahuja RK, 1993, NETWORK FLOWS THEORY

[4] A GENUINELY POLYNOMIAL PRIMAL SIMPLEX ALGORITHM FOR THE ASSIGNMENT PROBLEM [J].

AKGUL, M .

DISCRETE APPLIED MATHEMATICS, 1993, 45 (02) :93-115

[5]

[Anonymous], 2003, LINEAR FRACTIONAL PR

[6] ALTERNATING BASIS ALGORITHM FOR ASSIGNMENT PROBLEMS [J].

BARR, RS ;

GLOVER, F ;

KLINGMAN, D .

MATHEMATICAL PROGRAMMING, 1977, 13 (01) :1-13

[7]

Cunningham W. H., 1979, Mathematics of Operations Research, V4, P196, DOI 10.1287/moor.4.2.196

[8]

Dinkelbach Werner., 1967, Manage. Sci., V13, P492, DOI [DOI 10.1287/MNSC.13.7.492, 10.1287/mnsc.13.7.492]

[9] A PRIMAL SIMPLEX ALGORITHM THAT SOLVES THE MAXIMUM FLOW PROBLEM IN AT MOST NM PIVOTS AND O(N2M) TIME [J].

GOLDFARB, D ;

HAO, JX .

MATHEMATICAL PROGRAMMING, 1990, 47 (03) :353-365

[10] HYPERBOLIC 0-1 PROGRAMMING AND QUERY OPTIMIZATION IN INFORMATION-RETRIEVAL [J].

HANSEN, P ;

DEARAGAO, MVP ;

RIBEIRO, CC .

MATHEMATICAL PROGRAMMING, 1991, 52 (02) :255-263

← 1 2 3 →