Finding the optimal attainable precisions in quantum multi-parameter metrology is a non-trivial problem. One approach to tackling this problem involves the computation of bounds which impose limits on how accurately we can estimate certain physical quantities. One such bound is the Holevo Cramer-Rao bound on the trace of the mean squared error matrix. The Holevo bound is an asymptotically achievable bound when one allows for any measurement strategy, including collective measurements on many copies of the probe. In this work we introduce a new bound, the Nagaoka-Hayashi bound, for estimating multiple parameters simultaneously. We show that this bound can be efficiently computed by casting it as a semidefinite program. This is a tighter bound than the Holevo bound and holds when we are restricted to separable measurements, thus making it more relevant in terms of experimental accessibility. We illustrate our bound with several examples of collective measurements on finite copies of the probe. These results have implications for the necessary requirements to saturate the Holevo bound.