稀疏分派问题的O(mn+n^2logn)有效算法
O(mn+n 2logn) efficient algorithms for the spare assignments problem
摘要
Ｍ．Ｌ．Ｂａｌｉｎｓｋｉ等人提出的求解分派问题符号差算法中的选轴方法，其选轴时间为０（ｎ３），本文将给出该选轴方法的一个改进方法，对稀疏分派问题其改进时间为０（ｍｎ＋ｎ２ｌｏｇｎ）．
Balinskis signature method for the assignment problem require at most O(n 3) computational time to choose edges. In this paper,a signature method for the spare assignment problem is gived. It require at most O(mn+n 2log n ) time.
出处
《广西民族学院学报（自然科学版）》
CAS
1998年第3期1-3,共3页
Journal of Guangxi University For Nationalities(Natural Science Edition)
参考文献4
-
1Bazarma, Mokhtar S. , Jarris, John J. Linear programming and networkflows, 383-384.
-
2M. L, Balinski. A competitre (Dual) Simplex method for the assign-mentproblem. Mathematical Programming34 (1986), 125-141.
-
3E. Roohy-lalah Improverments to the theoretical efficieng of the network Simplex method. Ph. D. Thsis, Carleton university (ottawa 1981).
-
4D. Goldfarb. Efficient dual Simplex Algorithms for the assignment problem. Mathematical Programming 33 (1985), 187-203.
