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

摘要

We consider {\em profit-maximization} problems for {\em combinatorialauctions} with {\em non-single minded valuation functions} and {\em limitedsupply}. We obtain fairly general results that relate the approximability of theprofit-maximization problem to that of the corresponding {\emsocial-welfare-maximization} (SWM) problem, which is the problem of finding anallocation $(S_1,\ldots,S_n)$ satisfying the capacity constraints that hasmaximum total value $\sum_j v_j(S_j)$. For {\em subadditive valuations} (andhence {\em submodular, XOS valuations}), we obtain a solution with profit$\OPT_\swm/O(\log c_{\max})$, where $\OPT_\swm$ is the optimum social welfareand $c_{\max}$ is the maximum item-supply; thus, this yields an $O(\logc_{\max})$-approximation for the profit-maximization problem. Furthermore,given {\em any} class of valuation functions, if the SWM problem for thisvaluation class has an LP-relaxation (of a certain form) and an algorithm"verifying" an {\em integrality gap} of $\al$ for this LP, then we obtain asolution with profit $\OPT_\swm/O(\al\log c_{\max})$, thus obtaining an$O(\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 subadditivevaluations, and arbitrary valuations with unlimited supply. Our approach forthe latter problem also gives an $\frac{e}{e-1}$-approximation algorithm forthe multi-product pricing problem in the Max-Buy model, with limited supply,improving on the previously known approximation factor of 2.