## 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 |