Multi-target tracking is a fundamental task in radar-based perception, where the objective is to accurately estimate the trajectories of multiple moving targets. A principled method for evaluating trajectory estimation performance is the trajectory generalized optimal subpattern (TGOSPA) metric, but it can be expensive to compute. In this paper, we propose a new efficient method for approximating the TGOSPA metric based on graph-structured multi-marginal optimal transport. This is achieved by first showing that the linear programming relaxation of TGOSPA is closely connected to a structured multi-marginal optimal transport problem. Inspired by the recently popular Sinkhorn iterations, entropy regularization is used, which allows the optimal solution to be efficiently approximated via dual coordinate ascent. By leveraging the graph structure of the problem, the computational complexity for each iteration is linear in the number of targets in the ground truth, the number of targets in the estimate, and the number of time steps, respectively. Finally, the efficacy of our proposed method is demonstrated in a simulation study.