Study on the Hungarian algorithm for the maximum likelihood data association problem  

作　　者：Wang Jianguo He Peikun Cao Wei 

机构地区：[1]The Second Academy of China Aerospace Science & Industry Corp., Beijing 100854, P. R. China [2]Dept. of Electronic Engineering, Beijing Inst. of Technology, Beijing 100081, P. R. China

出　　处：《Journal of Systems Engineering and Electronics》2007年第1期27-32,共6页系统工程与电子技术（英文版）

基　　金：This project was supported by the National Natural Science Foundation of China (60272024).

摘　　要：A specialized Hungarian algorithm was developed here for the maximum likelihood data association problem with two implementation versions due to presence of false alarms and missed detections. The maximum likelihood data association problem is formulated as a bipartite weighted matching problem. Its duality and the optimality conditions are given. The Hungarian algorithm with its computational steps, data structure and computational complexity is presented. The two implementation versions, Hungarian forest （HF） algorithm and Hungarian tree （HT） algorithm, and their combination with the naYve auction initialization are discussed. The computational results show that HT algorithm is slightly faster than HF algorithm and they are both superior to the classic Munkres algorithm.A specialized Hungarian algorithm was developed here for the maximum likelihood data association problem with two implementation versions due to presence of false alarms and missed detections. The maximum likelihood data association problem is formulated as a bipartite weighted matching problem. Its duality and the optimality conditions are given. The Hungarian algorithm with its computational steps, data structure and computational complexity is presented. The two implementation versions, Hungarian forest （HF） algorithm and Hungarian tree （HT） algorithm, and their combination with the naYve auction initialization are discussed. The computational results show that HT algorithm is slightly faster than HF algorithm and they are both superior to the classic Munkres algorithm.

关 键 词：TRACKING Data association Linear programming Hungarian algorithm 

分 类 号：TN957.52[电子电信—信号与信息处理] TN959.6[电子电信—信息与通信工程]