Share Email Print

Proceedings Paper

Evaluation of optimizations of Murty's M-best assignment
Author(s): Qin Lu; Wenbo Dou; Radu Visina; Krishna Pattipati; Yaakov Bar-Shalom; Peter Willett
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 27 April 2018
PDF: 7 pages
Proc. SPIE 10646, Signal Processing, Sensor/Information Fusion, and Target Recognition XXVII, 106460B (27 April 2018); doi: 10.1117/12.2306486
Show Author Affiliations
Qin Lu, Univ. of Connecticut (United States)
Wenbo Dou, Univ. of Connecticut (United States)
Radu Visina, Univ. of Connecticut (United States)
Krishna Pattipati, Univ. of Connecticut (United States)
Yaakov Bar-Shalom, Univ. of Connecticut (United States)
Peter Willett, Univ. of Connecticut (United States)

Published in SPIE Proceedings Vol. 10646:
Signal Processing, Sensor/Information Fusion, and Target Recognition XXVII
Ivan Kadar, Editor(s)

© SPIE. Terms of Use
Back to Top