We thank Francis Bach for our helpful discussions on approximate solutions of
convex optimization problems, and Yaron Singer for his comments and
suggestions, and for insights into budget feasible mechanisms.