  Approximating the optimal social welfare while preserving truthfulness is a
well studied problem in algorithmic mechanism design. Assuming that the social
welfare of a given mechanism design problem can be optimized by an integer
program whose integrality gap is at most $\alpha$, Lavi and Swamy~\cite{Lavi11}
propose a general approach to designing a randomized $\alpha$-approximation
mechanism which is truthful in expectation. Their method is based on
decomposing an optimal solution for the relaxed linear program into a convex
combination of integer solutions. Unfortunately, Lavi and Swamy's decomposition
technique relies heavily on the ellipsoid method, which is notorious for its
poor practical performance. To overcome this problem, we present an alternative
decomposition technique which yields an $\alpha(1 + \epsilon)$ approximation
and only requires a quadratic number of calls to an integrality gap verifier.
