A GENUINELY POLYNOMIAL PRIMAL SIMPLEX ALGORITHM FOR THE ASSIGNMENT PROBLEM

被引：19

作者：

AKGUL, M

机构：

[1] Department of Industrial Engineering, Bilkent University, 06533 Bilkent, Ankara

来源：

DISCRETE APPLIED MATHEMATICS | 1993年 / 45卷 / 02期

关键词：

ASSIGNMENT PROBLEM; NETWORK SIMPLEX METHOD; LINEAR PROGRAMMING; POLYNOMIAL ALGORITHMS; STRONGLY FEASIBLE BASES; HIRSCH CONJECTURE;

D O I：

10.1016/0166-218X(93)90054-R

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a primal simplex algorithm that solves the assignment problem in 1/2n(n+3)-4 pivots. Starting with a problem of size 1, we sequentially solve problems of size 2,3,4,...,n. The algorithm utilizes degeneracy by working with strongly feasible trees and employs Dantzig's rule for entering edges for the subproblem. The number of nondegenerate simplex pivots is bounded by n-1. The number of consecutive degenerate simplex pivots is bounded by 1/2(n-2)(n+1). All three bounds are sharp. The algorithm can be implemented to run in O(n3) time for dense graphs. For sparse graphs, using state of the art data structures, it runs in O(n2 log n+nm) time, where the bipartite graph has 2n nodes and m edges.

引用

页码：93 / 115

页数：23

共 50 条

[1]

ACHATZ H, 1989, DUAL FOREST ALGORITH

[2] A SEQUENTIAL DUAL SIMPLEX ALGORITHM FOR THE LINEAR ASSIGNMENT PROBLEM [J].