Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply

We consider {\em profit-maximization} problems for {\em combinatorial auctions} with {\em non-single minded valuation functions} and {\em limited supply}. We obtain fairly general results that relate the approximability of the profit-maximization problem to that of the corresponding {\em social-welfare-maximization} (SWM) problem, which is the problem of finding an allocation $(S_1,\dots ,S_n)$ satisfying the capacity constraints that has maximum total value ${\sum }_j{v}_j(S_j)$. For {\em subadditive valuations} (and hence {\em submodular, XOS valuations}), we obtain a solution with profit ${\text{OPT}}_{\text{swm}}\mathrm{/}O(\log c_{\max })$, where ${\text{OPT}}_{\text{swm}}$ is the optimum social welfare and $c_{\max }$ is the maximum item-supply; thus, this yields an $O(\log c_{\max})$-approximation for the profit-maximization problem. Furthermore, given {\em any} class of valuation functions, if the SWM problem for this valuation class has an LP-relaxation (of a certain form) and an algorithm “verifying” an {\em integrality gap} of $\text{al}$ for this LP, then we obtain a solution with profit ${\text{OPT}}_{\text{swm}}\mathrm{/}O(\text{al}\log c_{\max })$, thus obtaining an $O(\text{al}\log c_{\max })$-approximation. For the special case, when the tree is a path, we also obtain an incomparable $O(\log m)$-approximation (via a different approach) for subadditive valuations, and arbitrary valuations with unlimited supply. Our approach for the latter problem also gives an $\frac{e}{e-1}$-approximation algorithm for the multi-product pricing problem in the Max-Buy model, with limited supply, improving on the previously known approximation factor of 2.