TY - GEN

T1 - Approximation algorithms for non-single-minded profit-maximization problems with limited supply

AU - Elbassioni, Khaled

AU - Fouz, Mahmoud

AU - Swamy, Chaitanya

N1 - Funding Information:
★ Supported in part by NSERC grant 327620-09 and an Ontario Early Researcher Award. 1 Omitted proofs can be found in the full version of the paper.

PY - 2010

Y1 - 2010

N2 - 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(logc 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 -approximation for the profit maximization problem for combinatorial auctions with arbitrary valuations, and an O(logc 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(logm)-approximation (via a different approach) for subadditive valuations, and arbitrary valuations with unlimited supply.

AB - 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(logc 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 -approximation for the profit maximization problem for combinatorial auctions with arbitrary valuations, and an O(logc 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(logm)-approximation (via a different approach) for subadditive valuations, and arbitrary valuations with unlimited supply.

UR - http://www.scopus.com/inward/record.url?scp=78650891602&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17572-5_39

DO - 10.1007/978-3-642-17572-5_39

M3 - Conference contribution

AN - SCOPUS:78650891602

SN - 3642175716

SN - 9783642175718

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 462

EP - 472

BT - Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings

T2 - 6th International Workshop on Internet and Network Economics, WINE 2010

Y2 - 13 December 2010 through 17 December 2010

ER -