In multi-object tracking, multiple objects generate multiple sensor measurements, which are used to estimate the objects’ state simultaneously. Since it is unknown from which object a measurement originates, a data association problem arises. Considering all possible associations is computationally infeasible for large numbers of objects and measurements. Hence, approximation methods are applied to compute the most relevant associations. Here, we focus on deterministic methods, since multi-object tracking is often applied in safety-critical areas. In this work we show that Herded Gibbs sampling, a deterministic version of Gibbs sampling, applied in the labeled multi-Bernoulli filter, yields results of the same quality as randomized Gibbs sampling while having comparable computational complexity. We conclude that it is a suitable deterministic alternative to randomized Gibbs sampling and could be a promising approach for other data association problems.