A polynomial-time approximation algorithm for joint probabilistic data association

Joint probabilistic data association (JPDA) is a powerful tool for solving data association problems. However, the exact computation of association probabilities {β_jk} in JPDA is NP-hard, where β_jk is the probability that j-th observation is from k-th track. Hence, we cannot expect to compute association probabilities in JPDA exactly in polynomial time unless P = NP. In this paper, we present a simple Markov chain Monte Carlo data association (MCMCDA) algorithm that finds an approximate solution to JPDA in polynomial time. For ε > 0 and 0 < η < .5, we prove that the algorithm finds good estimates of β_jk with probability at least 1 - η in time complexity O(ε^-2 log η^-1N(N log N + log ε^-1))), where N is the number of observations.