Offline and online algorithms for single-minded selling problem.

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 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. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an O (k) -approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an O (k ⋅ (log ⁡ h + log ⁡ k)) -competitive algorithm is given, where h is the highest unit item price among all buyers. [ABSTRACT FROM AUTHOR]