A fundamental problem in multi-target tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Here, this problem is formulated as a multi-dimensional assignment problem using gating techniques to introduce sparsity into the problem, filtering techniques to generate tracks which are then used to score each assignment of a collection of observations to its corresponding filtered track. Problem complexity is further reduced by decomposing the problem into disjoint components using graph theoretic methods. A recursive Lagrangean relaxation algorithm is then developed to obtain high quality suboptimal solutions in real-time. The algorithms are, however, applicable to a large class of sparse multi-dimensional assignment problems arising in general multi-target and multi-sensor tracking. Results of extensive numerical testing are presented for a case study to demonstrate the speed, robustness, and exceptional quality of the solutions.