Tracking multiple maneuvering targets in a cluttered environment is a challenging problem. A combination of interacting multiple model (IMM) and joint probabilistic data association (JPDA) has been successfully applied to track multiple maneuvering targets. In IMM, the motion of a maneuvering target is approximated by a finite number of simple, distinct kinematic models. However, the exact computation of the combined approach has the time complexity which is exponential in the numbers of kinematic models and measurements. When applying JPDA and IMM, the numbers of targets and kinematic models are known, so we can design a tracking system suitable for the given numbers of targets and kinematic models. But the number of measurements is not known in advance, and it poses a serious problem in computing association probabilities in JPDA. Hence, for a large problem, we need to seek for an efficient approximation algorithm. In this paper, we present a randomized algorithm which finds approximations of association probabilities with good fidelity and prove that the time complexity of the algorithm is polynomial in the size of the problem.