Efficient dual simplex algorithms for the assignment problem |
| |
Authors: | D Goldfarb |
| |
Institution: | (1) Department of Industrial Engineering and Operations Research, Columbia University, 10027 New York, NY, USA |
| |
Abstract: | Efficient algorithms based upon Balinski's signature method are described for solving then × n assignment problem. These algorithms are special variants of the dual simplex method and are shown to have computational bounds of O(n
3). Variants for solving sparse assignment problems withm arcs that require O(m) space and O(mn + n
2 logn) time in the worst case are also presented.This research was supported in part by the National Science Foundation under Grant No. MCS-8006064 and by the Army Research Office under Contracts No. DAAG 29-82-K0163 and DAAG 29-83-K0106 |
| |
Keywords: | Assignment Problem Dual Simplex Method Weighted Matching Optimization Sparsity Block Pivot |
本文献已被 SpringerLink 等数据库收录! |