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.