On Hardness of Pricing Items for Single-Minded Bidders
On Hardness of Pricing Items for Single-Minded Bidders
复制标题
论单一投标人定价项目的硬度
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Sviridenko
中科院分区：
文献类型：
--
作者：
R. Khandekar;T. Kimbrel;K. Makarychev;M. Sviridenko
我们考虑最近备受关注的以下项目定价问题。卖家有n件商品的无限数量的复印件。有m个买家，每个人都有预算，并打算购买固定的商品子集。给出物品的价格，每个买家以给定的价格购买他的物品子集，前提是子集的总价格至多是他的预算。卖家的目标是确定价格，使她的总利润最大化。
在本文中，我们主要研究买家对至多两个大小的子集感兴趣的情况。这种特殊情况是已知的APX-Hard(Guruswami等人[1])。Balcan和Blum提出的最著名的近似算法给出了一个4-近似[2]。我们表明，在他们的分析中使用的组合上界确实存在4的差距。我们进一步证明了，即使在这种特殊情况下，该问题的自然线性规划松弛也有4的积分间隙。然后，我们证明了在唯一的博弈猜想下，该问题在因子2内是NP-难逼近的，在因子17/16内是无条件NP-难逼近的。最后，我们将问题的APX-硬度推广到了以物品为顶点、买家为边的图是二部图的特殊情况。
我们希望我们的技术将有助于获得这个问题的更强的逼近界的坚硬性。
We consider the following item pricing problem which has received much attention recently. A seller has an infinite numbers of copies of n items. There are m buyers, each with a budget and an intention to buy a fixed subset of items. Given prices on the items, each buyer buys his subset of items, at the given prices, provided the total price of the subset is at most his budget. The objective of the seller is to determine the prices such that her total profit is maximized.
In this paper, we focus on the case where the buyers are interested in subsets of size at most two. This special case is known to be APX-hard (Guruswami et al [1]). The best known approximation algorithm, by Balcan and Blum, gives a 4-approximation [2]. We show that there is indeed a gap of 4 for the combinatorial upper bound used in their analysis. We further show that a natural linear programming relaxation of this problem has an integrality gap of 4, even in this special case. Then we prove that the problem is NP-hard to approximate within a factor of 2 assuming the Unique Games Conjecture; and it is unconditionally NP-hard to approximate within a factor 17/16. Finally, we extend the APX-hardness of the problem to the special case in which the graph formed by items as vertices and buyers as edges is bipartite .
We hope that our techniques will be helpful for obtaining stronger hardness of approximation bounds for this problem.