Improved hardness results for profit maximization pricing problems with unlimited supply

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 S _c ⊆ [n] of items of interest, together with a budget _c , 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 S _c , 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 single-minded pricing (SMP) problems. In the former problem, each customer c buys the cheapest item i ∈ S _c, if its price is no higher than the budget B _c, and buys nothing otherwise. In the latter problem, each customer c buys the whole set S _c if its total price is at most B _c , 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-δ}n-hard 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 S _c 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 S _c is a simple path in the graph. We show that Tollbooth Pricing is at least as hard to approximate as the Unique Coverage problem, thus obtaining an Ω(log ^ε n)-hardness of approximation, assuming NP ⊈ BPTIME(2 ^nδ), for any constant δ, and some constant ε depending on δ.