|
Murty’s ranking algorithm provides a clever way of partitioning the solution space to find the M best assignments, whose costs are in a nondecreasing order, to a linear assignment problem with an N N cost matrix, where total assignment cost is minimized. This paper reviews the optimization techniques for Murty’s M -best method combined with successive shortest path assignment algorithms (such as the Jonker and Volgenant assignment algorithm) from two papers. The first paper discussed three optimizations: 1) inheriting dual variables and partial solutions during partitioning, 2) sorting subproblems by lower cost bounds before solving, and 3) partitioning in an optimized order. The second paper proposed updating the dual variables of the previous solution before the shortest path procedure is applied to solve a subproblem without mentioning the use of lower cost bounds. One contribution of this paper is that we propose a much tighter lower bound than that given by the first paper. Comparative tests have been conducted among algorithms employing different combinations of the optimization techniques to evaluate their respective performances.
|
