  It was recently shown in [http://arxiv.org/abs/1207.5518] that revenue
optimization can be computationally efficiently reduced to welfare optimization
in all multi-dimensional Bayesian auction problems with arbitrary (possibly
combinatorial) feasibility constraints and independent additive bidders with
arbitrary (possibly combinatorial) demand constraints. This reduction provides
a poly-time solution to the optimal mechanism design problem in all auction
settings where welfare optimization can be solved efficiently, but it is
fragile to approximation and cannot provide solutions to settings where welfare
maximization can only be tractably approximated. In this paper, we extend the
reduction to accommodate approximation algorithms, providing an approximation
preserving reduction from (truthful) revenue maximization to (not necessarily
truthful) welfare maximization. The mechanisms output by our reduction choose
allocations via black-box calls to welfare approximation on randomly selected
inputs, thereby generalizing also our earlier structural results on optimal
multi-dimensional mechanisms to approximately optimal mechanisms. Unlike
[http://arxiv.org/abs/1207.5518], our results here are obtained through novel
uses of the Ellipsoid algorithm and other optimization techniques over {\em
non-convex regions}.
