Improved hardness results for profit maximization pricing problems with unlimited supply

Parinya Chalermsook*, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

35 Citations (Scopus)


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 ), for any constant δ, and some constant ε depending on δ.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings
Number of pages12
Volume7408 LNCS
Publication statusPublished - 2012
MoE publication typeA4 Article in a conference publication
EventInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems - Cambridge, United States
Duration: 15 Aug 201217 Aug 2012
Conference number: 15

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7408 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


WorkshopInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Abbreviated titleAPPROX
Country/TerritoryUnited States


Dive into the research topics of 'Improved hardness results for profit maximization pricing problems with unlimited supply'. Together they form a unique fingerprint.

Cite this