科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider the revenue maximization problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly d(i) items, and each item j gives a benefit vu to buyer i. In particular, each item j has a quality q(j), each buyer i has a value vi and the benefit v(ij) is defined as the product v(i)q(i). The problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, i.e., the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility, defined as the benefit of all the items in the bundle minus their purchase prices, by receiving any different bundle. We first prove that the problem cannot be approximated within a factor of O(m(1-is an element of)), for any is an element of > 0, unless P = NP and that this result is asymptotically tight. In fact, we show that a simple greedy algorithm provides an m-approximation of the optimal revenue (this approximation guarantee holds even for the generalization in which the benefits vu are completely arbitrary.). Then, we focus on an interesting subclass of "proper" instances, i.e., not containing buyers (useless buyers) who are a priori known to be not able to receive any bundle. For these instances, we design an interesting 2-approximation algorithm and show that no better approximation is possible unless P = NP. We stress that it is possible to efficiently check if an instance is proper and, if discarding useless buyers is allowed, an instance can be made proper in polynomial time without worsening the value of its optimal solution.
- 出版日期2017-2-1
