27 April 2018 Evaluation of optimizations of Murty's M-best assignment
Author Affiliations +
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.
Conference Presentation
© (2018) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Qin Lu, Qin Lu, Wenbo Dou, Wenbo Dou, Radu Visina, Radu Visina, Krishna Pattipati, Krishna Pattipati, Yaakov Bar-Shalom, Yaakov Bar-Shalom, Peter Willett, Peter Willett, "Evaluation of optimizations of Murty's M-best assignment", Proc. SPIE 10646, Signal Processing, Sensor/Information Fusion, and Target Recognition XXVII, 106460B (27 April 2018); doi: 10.1117/12.2306486; https://doi.org/10.1117/12.2306486


Back to Top