Approximation and Competitive Algorithms for Single-Minded Selling Problem

摘要

The problem of item selling with the objective of maximizing the revenue is studied. Given a seller with k types of items and n single-minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must carefully assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer b_i is associated with a value function V_i(·) such that V_i(x) is the accepted unit bundle price b_i is willing to pay for x bundles. We show that the single-minded item selling problem is NP-hard. Moreover, we give an O(k~(1/2))-approximation algorithm. For the online version, i.e., the buyers come one by one and the decision on each buyer must be made before the arrival of the next buyer, an O(k~(1/2) • (log h + log k))-competitive algorithm is achieved, where h is the highest unit item price among all buyers.