• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >A Recursive Method for Solving Assignment Problems
【24h】

A Recursive Method for Solving Assignment Problems

机译：一种求解指派问题的递推方法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The recursive algorithm is a polynomially bounded nonsimplex method for solving assignment problems. It begins by finding the optimum solution for a problem defined from the first row, then finding the optimum for a problem defined from rows one and two, etc., continuing until it solves the problem consisting of all the rows. It is thus a dimension expanding rather than an improvement method such as as the simplex. During the method the row duals are non-increasing and the column duals non-decreasing. Best and worst case behavior is analyzed. It is shown that some problems can be solved in one pass through the data, while others may require many passes. The number of zero shifts (comparable to degenerate pivots in the primal method) is shown to be at most n-squared/2. Extensive computational experience on the DEC-20 computer shows the method to be competitive for at least some kinds of assignment problems. Further tests on other computers are planned. (Author)

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号