  We derive a necessary and sufficient condition for the possibility of
achieving the Heisenberg scaling in general adaptive multi-parameter estimation
schemes in presence of Markovian noise. In situations where the Heisenberg
scaling is achievable, we provide a semidefinite program to identify the
optimal quantum error correcting (QEC) protocol that yields the best estimation
precision. We overcome the technical challenges associated with potential
incompatibility of the measurement optimally extracting information on
different parameters by utilizing the Holevo Cram\'er-Rao (HCR) bound for pure
states. We provide examples of significant advantages offered by our joint-QEC
protocols, that sense all the parameters utilizing a single error-corrected
subspace, over separate-QEC protocols where each parameter is effectively
sensed in a separate subspace.
