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 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 δ.
Original language | English |
---|---|
Title of host publication | Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings |
Pages | 73-84 |
Number of pages | 12 |
Volume | 7408 LNCS |
DOIs | |
Publication status | Published - 2012 |
MoE publication type | A4 Article in a conference publication |
Event | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems - Cambridge, United States Duration: 15 Aug 2012 → 17 Aug 2012 Conference number: 15 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 7408 LNCS |
ISSN (Print) | 03029743 |
ISSN (Electronic) | 16113349 |
Workshop
Workshop | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems |
---|---|
Abbreviated title | APPROX |
Country/Territory | United States |
City | Cambridge |
Period | 15/08/2012 → 17/08/2012 |