  We provide polynomial-time approximately optimal Bayesian mechanisms for
makespan minimization on unrelated machines as well as for max-min fair
allocations of indivisible goods, with approximation factors of $2$ and
$\min\{m-k+1, \tilde{O}(\sqrt{k})\}$ respectively, matching the approximation
ratios of best known polynomial-time \emph{algorithms} (for max-min fairness,
the latter claim is true for certain ratios of the number of goods $m$ to
people $k$). Our mechanisms are obtained by establishing a polynomial-time
approximation-sensitive reduction from the problem of designing approximately
optimal {\em mechanisms} for some arbitrary objective ${\cal O}$ to that of
designing bi-criterion approximation {\em algorithms} for the same objective
${\cal O}$ plus a linear allocation cost term. Our reduction is itself enabled
by extending the celebrated "equivalence of separation and
optimization"[GLSS81,KP80] to also accommodate bi-criterion approximations.
Moreover, to apply the reduction to the specific problems of makespan and
max-min fairness we develop polynomial-time bi-criterion approximation
algorithms for makespan minimization with costs and max-min fairness with
costs, adapting the algorithms of [ST93], [BD05] and [AS07] to the type of
bi-criterion approximation that is required by the reduction.
