首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号