Abstract. We consider profit maximization pricing problems, where we are given a set of m customers and a set of n items. Each customer c is associated with a subset Sc ⊆ [n] of items of interest, together with a budget Bc, and we assume that there is an unlimited supply of each item. Once the prices are fixed for all items, each customer c buys a subset of items in Sc, according to its buying rule. The goal is to set the item prices so as to maximize the total profit. We study the unit-demand min-buying pricing (UDP MIN ) and the singleminded pricing (SMP) problems. In the former problem, each customer c buys the cheapest item i ∈ Sc, if its price is no higher than the budget Bc, and buys nothing otherwise. In the latter problem, each customer c buys the whole set Sc if its total price is at most Bc, and buys nothing otherwise. Both problems are known to admit O(min {log(m + n), n})-approximation algorithms. We prove that they are log 1− (m + n) hard to approximate for any constant , unless NP ⊆ DTIME(n log δ n ), where δ is a constant depending on . Restricting our attention to approximation factors depending only on n, we show that these problems are 2 log 1−δ nhard to approximate for any δ > 0 unless NP ⊆ ZPTIME(n log δ n ), where δ is some constant depending on δ. We also prove that restricted versions of UDP MIN and SMP, where the sizes of the sets Sc are bounded by k, are k 1/2− -hard to approximate for any constant . We then turn to the Tollbooth Pricing problem, a special case of SMP, where each item corresponds to an edge in the input graph, and each set
The logarithmic approximation is essentially tight: Chalermsook et al. show for any constant > 0 there is no O(log 1− (m + n))-approximation unless NP ⊆ DTIME(n polylog(n) ) REF .
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
APPROX-RANDOM
Mathematics Computer Science