A sequential dual simplex algorithm for the linear assignment problem |
| |
Institution: | 1. State Key Laboratory of Water Resources and Hydropower Engineering Science, Wuhan University, Wuhan 430072, China;2. School of Civil Engineering, Jiangxi University of Technology, Nanchang 330098, China |
| |
Abstract: | We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski 3,4] and Goldfarb 8]: O(n2) pivots, O(n2 log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|