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

We consider

profit-maximization

problems for

combinatorial auctions

with

non-single minded valuation functions

and

limited supply

. We obtain fairly general results that relate the approximability of the profit-maximization problem to that of the corresponding

social-welfare-maximization

(SWM) problem, which is the problem of finding an allocation (

S

1

,...,

S

n

) satisfying the capacity constraints that has maximum total value ∑ 

j

v

j

(

S

j

). Our results apply to both structured valuation classes, such as

subadditive valuations

, as well as

arbitrary valuations

. For subadditive valuations (and hence

submodular, XOS valuations

), we obtain a solution with profit

, where

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

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

integrality gap

of

α

for this LP, then we obtain a solution with profit

, thus obtaining an

O

(

α

\log c_{\max})-approximation. The latter result implies an

$O(\sqrt m\log c_{\max})$

-approximation for the profit maximization problem for combinatorial auctions with

arbitrary valuations

, and an

O

(log

c

max

)-approximation for the non-single-minded

tollbooth problem

on trees. 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.