Approximation Algorithms for the Max-Buying Problem with Limited Supply

الأصل · EN

We consider the Max-Buying Problem with Limited Supply, in which there are n items, with Cᵢ copies of each item i, and m bidders such that every bidder b has valuation vib for item i. The goal is to find a pricing p and an allocation of items to bidders that maximizes the profit, where every item is allocated to at most Cᵢ bidders, every bidder receives at most one item and if a bidder b receives item i then pᵢ ≤ vib. Briest and Krysta presented a 2-approximation for this problem and Aggarwal et al. presented a 4-approximation for the Price Ladder variant where the pricing must be non-increasing (that is, p₁ ≥ p₂ ≥ ≥ pₙ). We present an e/(e-1)-approximation for the Max-Buying Problem with Limited Supply and, for every ε > 0, a (2+ε)-approximation for the Price Ladder variant.